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

/*
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 ;
        }
    }
};