题解 | #二叉树的下一个结点#

暴力解法当然就是按照中序遍历一遍，但这题中参数只给了待查找的子树根节点，中序遍历操作过于麻烦，最好是从子树根节点直接开始查找。

1. 如果子树根节点存在右节点，则从该右节点开始，一路向左查找；

2. 否则，子树根节点的中序遍历下一个节点只能在其父辈中查找，并且只有将当前根节点作为左节点的父节点符合条件：

   1. 往上查找，找到第一个把当前根节点当做左子节点的父节点；

   2. 如果不存在，则待查找子树根节点是该树中序遍历的最后一个节点，返回NULL。

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