二叉树的下一个节点

题意简述

给定一棵二叉树，和其中的一个节点，找到这个节点的中序后继，要求 $O(1) space, O(n) time$

解法

记给定的节点为 p, 如果 p 有右子树，那么显然中序后继就是右子树中最左的节点，如果没有右子树，又分为几种情况：
1. 给定节点本身是根节点，而且又没有右子树，那么没有中序后继
2. 给定节点是其父节点的左子树根，那么中序后继就是父节点
3. 给定节点是其父节点的右子树根，那么向上回溯，直到当前节点是其父节点的左子树根为止，其后继是该节点的父节点。

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(pNode->right != NULL){
            TreeLinkNode* p = pNode->right;
            while(p->left != NULL){
                p = p->left;
            }
            return p;
        }

        if(pNode->next == NULL)return NULL;

        if(pNode == pNode->next->left)return pNode->next;

        TreeLinkNode* p = pNode;
        while(p->next != NULL && p != p->next->left){
            p = p->next;
        }
        if(p->next == NULL)return NULL;
        return p->next;
    }
};