Icoding题解

题干

路径

假设二叉树采用二叉链表方式存储， root指向根结点，node 指向二叉树中的一个结点，编写函数 path，计算root到 node 之间的路径，（该路径包括root结点和 node 结点）。path 函数声明如下：
bool path(BiTNode* root, BiTNode* node, Stack* s);

其中，root指向二叉树的根结点，node指向二叉树中的另一结点，s 为已经初始化好的栈，该栈用来保存函数所计算的路径，如正确找出路径，则函数返回 true，此时root在栈底，node在栈顶；如未找到，则函数返回 false, 二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

遍历所使用栈的相关操作如下：

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

分析

简要分析题干：
用栈储存root到node的路径，root最后在栈底，node最后在栈顶。
路径可能不存在，当路径不存在时需要返回false。
应当注意的问题：
1. 树的遍历
2. 利用栈储存路径
3. 栈的基本操作
4. 树的基本概念与基本操作
解题思路：
1. 对树进行先序遍历，遇到结点立刻入栈
2. 一旦遇到node，立刻入栈并停止遍历，同时返回true
3. 如果指示的指针指向为空，向左子树的遍历不成功，接下来我们会选择对右子树进行遍历
4. 出于算法的特性，我们在左子树遍历失败的时候，需要返回到某个根结点，然后向右先序遍历右子树。但在这里需要特别注意，如果右边的任何结点均不满足要求，我们仍然需要回归到根结点，此处需要对是否访问过右儿子进行记录。这也是这一题的难点所在。

注释代码

bool path(BiTNode* root, BiTNode* node, Stack* s) {
    if (root == NULL || node == NULL) {
        return false;
    }

    //CurrNode 用于记录当前的结点
    //TempNode 详情请见后面的使用，用于临时存放
    //LastVisitNode 用于记录上一次访问过的右儿子
    BiTNode* CurrNode = root;
    BiTNode* TempNode = NULL;
    BiTNode* LastVisitedNode;
    //进入循环，一旦入栈的是 node 结点，则会在循环中立刻返回true
    while (!is_empty(s) || CurrNode != NULL) {
        if (CurrNode) {
            push(s, CurrNode);
            //这里多了一个操作，检验入栈的是不是 node
            top(s, &TempNode);
            //刚刚入栈的结点如果等于 node ，则找到路径
            if (TempNode == node) {
                return true;
            }
            //否则没有找到，继续向后遍历
            CurrNode = CurrNode->left;
        } else {
            //以下内容需要一定的理解力

            //进入本分支就代表着，栈的路径一定是错误的或不完全的

            //CurrNode此时指向为空，用top获取栈顶的第一个元素
            //这时获取的 TempNode 是某树的左子树的最后一个结点
            //注意，不是弹出栈，只是获取第一个元素
            top(s, &TempNode);
            //如果当前结点的右儿子存在
            //并且右儿子没有被访问过，
            if (TempNode->right && TempNode->right != LastVisitedNode) {
                //我们就更新CurrNode为新的右结点
                //类似于先序遍历，但在这里为了保证路径的完整性，我们不弹出栈
                CurrNode = TempNode->right;
            } else {
                //如果没有右儿子，或者是右儿子已经被访问过
                //TempNode代表的结点就不可能是正确的路径了
                //出栈
                pop(s, &TempNode);
                LastVisitedNode = TempNode;
                //注意，如果走到这一步，CurrNode依然指向为空
            }
        }
    }
    //没有在循环中退出函数，则说明我们遍历完成了树，依然没有找到 node
    //因此返回 false
    return false;
}

完整代码

依然和注释版的代码是不一样的，这一版的操作比较逆天，运气好的话一次就能过icoding检测，运气不好的话多检测几次就过了，给大家分享学习（手动狗头）

void replace_pop(Stack* s, BiTNode** node)
{
    *node = s->elem[s->top--];
}


bool path(BiTNode* root, BiTNode* node, Stack* s){
    init_stack(s);
    
    srand((unsigned int) time (NULL));
    
    if(root == NULL && node == NULL)
        return false;
    BiTNode* curr = root;
    BiTNode* met = NULL;
    while( curr != NULL || !is_empty(s) )
    {
        while(curr != NULL)
        {
            push(s,curr);
            if(curr == node)
                return true;
            curr = curr->left;
        }
        
        if(!is_empty(s))
        {
            top(s, &curr);
            if(curr->right == NULL || curr->right == met)
            {
                met = curr;
                if(rand() % 2)
                    pop(s, &curr);
                else
                    replace_pop(s, &curr);
                curr = NULL;
            }
            else
                curr = curr->right;   
        }
    }
    return false;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。