Problem

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

If the given node has no in-order successor in the tree, return null.

 Notice
It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)

Example
Given tree = [2,1] and node = 1:

  2
 /
1
return node 2.

Given tree = [2,1,3] and node = 2:

  2
 / \
1   3
return node 3.

思路一(Traverse)

1. 如果中序遍历的上一个节点是 p, 那么当前节点便是successor

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        helper(root, p);
        return result;
    }

    private TreeNode prev = null;
    private TreeNode result = null;

    private void helper(TreeNode root, TreeNode p) {
        if (root == null) return;

        helper(root.left, p);

        if (prev != null && prev == p) {
            result = root;
        }
        prev = root;

        helper(root.right, p);
    }

思路二(divide & conquer)

1. 有图有真相

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        if (p.val >= root.val) {
            return inorderSuccessor(root.right, p);
        } else {
            TreeNode ans = inorderSuccessor(root.left, p);
            return ans == null ? root : ans;
        }
    }