510.二叉搜索树中的中序后继 II (Medium)*

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if(node == nullptr) {
            return nullptr;
        }
        // 右子树为空则结果为以此子树为左子树的第一个结点
        if(node->right == nullptr) {
            while(node->parent != nullptr) {
                auto root = node->parent;
                if(root->left == node) {
                    return root;
                }
                node = root;
            }
        }else {
            auto p = node->right;
            while(p->left != nullptr) {
                p = p->left;
            }
            return p;
        }
        return nullptr;
    }
};