【剑指offer57 二叉树的下一个节点】

题目描述

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

 

 

如果当前节点有右子树，那么就是往右再一直往左就找到了

如果当前节点右子树为空，那么往上找父节点，一直找到当前节点为父节点的左子树为止

另一种情况就是当前节点就是中序遍历的最后一个节点了，那么往上找到根节点就会返回null

/*
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)return NULL;
        TreeLinkNode *ans = new TreeLinkNode(0);
        if(pNode->right){
            ans = pNode->right ;
            while(ans && ans->left)ans=ans->left;
            return ans;
        }
        //没有右子树
        if(!pNode->right && pNode->next){
            TreeLinkNode *parrent = pNode->next;
            TreeLinkNode *cur = pNode;
            while(parrent && cur == parrent->right ){//
                cur = parrent; parrent = cur->next;
            }
            //如果是空了退出 结果就为空
            //如果是cur == parrrent->left  那就是parrent
            ans = parrent ;
            return ans ;
        }
    }
};