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

//存在右子树时，中序遍历下一个节点为右子树的左叶
//不存在右子树时，中序遍历下一个节点为该节点所在左子树的最近根节点
/*
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 nullptr;
        
        if (pNode->right) {    //如果有右子树，则中序遍历下一个节点为右子树的左叶
            pNode = pNode->right;
            while (pNode->left) pNode = pNode->left;
            return pNode;
            
        } else if (pNode->next) {    //找到节点所在左子树的最近根节点，否则返回空
            TreeLinkNode *next = pNode->next;    //上一层节点
            while (next && next->left != pNode) {
                pNode = next;
                next = pNode->next;
            }
            
            if (next && next->left == pNode) return next;
        }
        
        return nullptr;
    }
};