285. Inorder Successor in BST

https://stackoverflow.com/questions/5471731/in-order-successor-in-binary-search-tree

Version #1 Iterative
看上去很fancy，实际上看成是 binary search就很好理解了
if (mid <= target) start = mid + 1
if (mid > target) end = mid

12.79 %
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        /* target = 4
          7
         / \
        3   8
       / \
      2   5
     /   / \
    1   4   6
    Why 5 should replace 7? Since 5 is the seconde time I walk left to approach 4, it is smaller than 7 and can be guaranteed to be larger than 4
        */
        // if a node has a right subtree, its sucessor is the left most node of its right butbree
        // if a node doesn't have a right subtree, result is the 1st ancestor on its right
        TreeNode result = null;
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val > p.val) { // p is in left subtree
                result = curr;
                curr = curr.left;
            } else if (curr.val <= p.val) {
                curr = curr.right;
            }
        }
        return result;
    }
}


一刷
100.00 %
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode curr = root;
        TreeNode result = null;
        while (curr != null) {
            if (curr.val > p.val) {
                result = curr;
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return result;
    }
}

二刷
Time O(n)
这个方法实际上是在找binary tree的next node，没有利用BST的性质
如果利用BST的性质recursiveily可以达到O(logn)
Version #2 Recursive
7.58 %
class Solution {
    TreeNode prev;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return dfs(root, p);
    }
    private TreeNode dfs(TreeNode node, TreeNode p) {
        if (node == null) return null;
        TreeNode left = dfs(node.left, p);
        if (left != null) return left;
        if (prev == p) {
            return node;
        }
        prev = node;
        TreeNode right = dfs(node.right, p);
        if (right != null) return right;
        return null;
    }
}