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

基本思路：

• 如果有右子树，找右子树中的最左节点
• 如果没有右子树，向上遍历直到根节点或者为某个树的左子树，中序遍历下一个节点即为该左子树的根节点

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (!pNode) return nullptr;
        TreeLinkNode* res;
        if (pNode->right) {
            res = pNode->right;
            while (res->left) res = res->left;
            return res;
        }
        res = pNode;
        while (res->next && res == res->next->right) res = res->next;
        return res->next;
    }
};