285. Inorder Successor in BST

Med Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.

Thoughts

找BST中给定节点p中序遍历后续一个结点。中序遍历后续一个节点有两种情况1. p的parent；2. p右子节存在的话，即p右节点捅到最深的左节点。根据BST的性质遍历并记录下parent，能很快定位到p节点。当p->val小于cur->val时往左遍历，并设置pre，否则往右遍历，这样到p后如右节点存在会一直捅到底。

Code

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *cur = root, pre = nullptr;
        while (cur != nullptr) {
            if (p->val < cur->val) {
                pre = cur;
                cur = cur->left;
            } else {
                cur = cur->right;
            } 
        }
        return pre;
    }
};

Analysis

找parent和右子树的最左结点一共遍历了h个结点，h为树高。所以复杂度为O(h).