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

根据中序遍历的规则，可以知道，当该结点有右子树时，返回其右子树最左边的结点。当该结点没有右子树时，则需要向上寻找第一个其左子树中包含该结点的结点。
根据这两种需求，分别写两个函数，一个通过递归找最左边的子结点，一个通过递归找向上第一个在左子树中包含该结点的点。
根结点由于其next域为空所以需要做特殊处理。

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