二叉树的下一个结点

• 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
• 根据中序遍历的定义，分情况讨论即可：
  • 如果当前节点pNode有右孩子，只需找右孩子的最左孩子，若没有则是该右孩子；
  • 如果pNode有父节点且它是左孩子，则结果为父节点；
  • 如果pNode有父节点且它是右孩子，则应该一直往上找父节点，直到该pNode不在该节点的左子树中。

/*
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 == nullptr) return nullptr;
        else if(pNode->right)
        {
            TreeLinkNode * p = pNode->right;
            while(p->left)
                p = p->left;
            return p;
        }
        else if(pNode->next && pNode->next->right == pNode){
            TreeLinkNode * p = pNode;
            while(p->next && p->next->right == p)
                p=p->next;
            return p->next;    
        }
        else if(pNode->next && pNode->next->left == pNode)
            return pNode->next;
        else return nullptr;
        
    }
};