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

题目给定结点，求按照中序遍历的顺序，它的下一个结点是什么，除了left和right指针外，还是指向父结点的next指针。
最容易想到的暴力解法：
1、根据next，找到根结点；
2、递归获得中序遍历序列；
3、找到给定的结点，输出下一个结点即可；

改进解法（我之前没注意pNode是给定结点，一直以为是根结点，浪费了大量时间）
找规律：
1、若右孩子存在，找右孩子中最左边的结点，没有则返回右孩子；
2、若右孩子不存在，那么就需要考虑父结点问题，父结点又分为左孩子和右孩子，两者是不一样的。若是父结点的左孩子，那么它的下一个结点为父结点，若不是，那么根据中序遍历，当前父结点已经遍历过了，只能向上找父结点的父结点。重复上述过程；
3、若是尾结点，输出nullptr；
代码：

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode)
            return NULL;

        if(pNode->right){
            pNode = pNode->right;
            while(pNode->left){
                pNode = pNode->left;
            }
            return pNode;
        }

        while(pNode->next){
            TreeLinkNode* root = pNode->next;
            if(root->left == pNode)
                return root;
            pNode = pNode->next;
        }

        return nullptr;
    }
};