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

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/

/*
分三种情况：
1. 该节点有右子，直接找到右子树中的最左节点，并返回
2. 该节点无右子树
	1.该节点在其父节点的左树：直接返回其父节点
	2.在其父节点的右树，一直向父节点找。
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode)
        {   
            return nullptr;
        }

        TreeLinkNode *pnext=nullptr;
        
        if(pNode->right)
        {   
            TreeLinkNode *pr=pNode->right;
            while(pr->left)
            {   
                pr=pr->left;
            }
            pnext=pr;
        }
        else if(pNode->next)
        {           
            TreeLinkNode *pcur=pNode;
            while(pcur->next&&pcur==pcur->next->right)
            {       
                pcur=pcur->next;
            }
            pnext=pcur->next;
        }
    return pnext;
    }
};