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

两行搞定。

/*
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) {
        TreeLinkNode* pDes = nullptr;
        
        if(!pNode->next){//for middle node
            TreeLinkNode* pR = pNode->right;
            if(!pR) return nullptr;
            if(!pR->left) return pR;
            else{
                while(pR->left){
                    pR=pR->left;
                }
                return pR;
            }
        }
        else if(pNode->next->left == pNode){//left node
            if(pNode->right) return pNode->right;
            else return pNode->next;
        }
        else{//right node
            if(pNode->right) return pNode->right;
            else if(!pNode->next->next) return nullptr;
            else if(pNode->next->next->left == pNode->next)
                return pNode->next->next;
            else{
                TreeLinkNode* pN = pNode->next->next;
                while(pN->next && pN->next->right == pN){
                    pN = pN->next;
                }
                if(!pN->next) return nullptr;
                else return pN->next;
            }
                return nullptr;
        }
    }
};