题目描述

• 给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？
• 树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;      // 左孩子
    struct TreeLinkNode *right;     // 右孩子 
    struct TreeLinkNode *next;      // 父节点
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};

题目解读

• 剑指Offer 65

代码

class Solution {
    public:
        TreeLinkNode* GetNext(TreeLinkNode* pNode){
            TreeLinkNode *p, *c, *next;

            if(pNode == NULL){
                return NULL;
            }
            // 如果该节点有右子树
            if(pNode->right != NULL){
                p = pNode->right;
                while(p->left != NULL){
                    p = p->left;
                }
                next = p;
            }   // 执行 else if 证明该节点没有右子树
            else if(pNode->next != NULL){ 
                p = pNode->next;
                c = pNode;
                while(p!=NULL && c == p->right){
                    c = p;
                    p = p->next;
                }
                next = p;
            }
            return next;
        }
};

总结展望

• 看书思路不难，容易理解，然后自己手写了；但是，我认为我的代码没问题，没想到提交到牛客网报错为段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起，实在是不知道为啥，留待以后第二遍再来解决吧...
  (出错代码在下面已更正 2019/3/3)
• 上面跑正确这个代码是参考别人正确代码写的，写的确实不错，比我的简洁！

附录

• 自己手动写的出错代码，有待修改
  段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起

// 因为指针为空，出错代码
class Solution {
    public:
        TreeLinkNode* GetNext(TreeLinkNode* pNode){
            TreeLinkNode *p;

            if(pNode == NULL){
                return NULL;
            }
            
            //１，节点有右子树
            if(pNode->right != NULL){
                p = pNode->right;
                //现在两种情况
                // 1.1 右子树没有左节点，则右子树根节点即为中序遍历下一个节点
                if(p->left == NULL){
                    return p;
                }
                else{ // 1.2 右子树有左节点，则沿着右子节点出发一直沿着指向左子节点的指针行进
                    while(p->left != NULL){
                        p = p->left;
                    }
                    return p;
                }
            }
            else // ２　节点没有右子树
            {    // 2.1 节点是它父节点的的左子节点，那么它的下一个节点就是它的父节点
                p = pNode->next;
                if(pNode == p->left){    // 如果p为空呢，这就是出错点，指针为空，下面为修改之后代码
                    return pNode->next;
                }
                else // 2.2 如果一个节点既没有右子树，并且它还是它父节点的右子节点，
                {    //那么沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点
                    while(pNode->next != NULL){
                        p = pNode->next;
                        if(p->left == pNode){
                            return p;
                        }
                        pNode = pNode->next;
                    } 
                    return NULL;
                }
            }
            
        }
};

• 修正之后的代码

// 更正之后的代码
class Solution {
    public:
        TreeLinkNode* GetNext(TreeLinkNode* pNode){
            TreeLinkNode *p;

            if(pNode == NULL){
                return NULL;
            }
            
            //１，节点有右子树
            if(pNode->right != NULL){
                p = pNode->right;
                //现在两种情况
                // 1.1 右子树没有左节点，则右子树根节点即为中序遍历下一个节点
                if(p->left == NULL){
                    return p;
                } // 1.2 右子树有左节点，则沿着右子节点出发一直沿着指向左子节点的指针行进
                else {
                    while(p->left != NULL){
                        p = p->left;
                    }
                    return p;
                }
            }
            else {  // ２　节点没有右子树
                p = pNode->next;
                if(p != NULL){
                    // 2.1 节点是它父节点的的左子节点，那么它的下一个节点就是它的父节点
                    if(pNode == p->left){
                        return pNode->next;
                    }
                    else // 2.2 如果一个节点既没有右子树，并且它还是它父节点的右子节点，
                    {    //那么沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点
                        while(pNode->next != NULL){
                            p = pNode->next;
                            if(p->left == pNode){
                                return p;
                            }
                            pNode = pNode->next;
                        }
                        return NULL;
                    }
                }
                else{
                    return p;
                }
            }
        }
};