题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路

通过举例子不难发现以下几个规律：
(1) 节点为空指针，返回空指针
(2) 节点有右孩子，则返回它的右孩子的最左
(3) 节点没有右孩子：

• 如果它是它父亲的左孩子，那就返回它的父亲
• 如果它是它父亲的右孩子，那就看它的父亲的情况：它的父亲如果是左孩子，就返回父亲的父亲，如果它的父亲是右孩子，那就再往上看父亲的情况

这里要说一个树里比较常见的被忽视的问题：会经常有段错误的问题，一般都是因为越界了(就是对NULL取它的左/右/根了)，在写->left的时候一定要注意看它的左会不会取到空

代码

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {

        if(pNode==NULL)
            return NULL;
        if(pNode->right!=NULL)   //如果节点有右子树，返回右子树的最左
        {
            pNode=pNode->right;
            while(pNode->left!=NULL)
            {
                pNode=pNode->left;
            }
            return pNode;
        }
        //如果节点没有右子树，就要看是它父亲的左孩子还是右孩子；
        //如果是左孩子，就返回它的父节点；如果是右孩子，就要看它的父节点是左孩子还是右孩子(重复上面的操作)
        //TreeLinkNode* pFather=pNode->next;   //创建一个父节点，这个不是整棵树的根
        while(pNode->next!=NULL)
        {
            if(pNode->next->left==pNode)//如果父节点是左，就返回父节点的父节点
                return pNode->next;
            pNode=pNode->next;
        }
        //遍历到了最上面，也就是父节点现在是整个树的根节点
        return NULL;
    }
};