Iterative:

  • If current node’s value is less than or equal to p’s value, answer must be in the right subtree.(注意等号的时候successor肯定在右边，这个等号的情况并不是随便放在哪个if中都一样,只能放在right那个sub中)
  • 当前node的值比p的值要大，往左边递归；root = root.left; 而此时successor也缩小了范围: 因为是BST, 所以当前节点是目前能确定的比左子树中所有值都大的最小值。
  • each null, our search is over, just return the candidate.
1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
    while (root != null) {
        if (p.val < root.val) {
            succ = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

Recursive:

实话说，这个方法种类太多，而且容易错，不推荐。

  1. p.val >= root.val: 此时的 successor 肯定是在右边的，所以直接右子树递归；
  2. p.val < root.val: 很多种情况:
  • p是root的左子节点，p可能有左子节点，可能没有左子节点；
  • root是p的右子节点: p的right child有可能有left subtree, 可能没有
1
2
3
4
5
6
7
8
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) return null;
    if (root.val <= p.val) return inorderSuccessor(root.right, p);
    else {
        TreeNode left = inorderSuccessor(root.left, p);
        return (left != null) ? left : root;
    }
}