Lowest Common Ancestor of a Binary Search Tree

• Easy
• keyword: Recursion
• 类似: Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia:

• The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

先做一下: Lowest Common Ancestor of a Binary Tree (并不平衡)

• 注意这个区别, 这里并不是BST而是一般的Binary Tree, 那么它的node可以相等. 所以并不应该比较val, 而是应该比较reference.
• 经典的walk-up/down tree recursion的题目, 之前参考leet1337做过好几次了.

• 思路就是, LCA有2种情况

  1. 若是p,q在同一个subtree, 那么以第一个遇到的node就是LCA了.
  2. 若是p,q不在同一个subtree, 那么LCA就是最上面的node的parent.

• 由于没有parent pointer, 所以要用递归(或者可以把parent也作为参数传下来, 于是使用iteration?)

  • 向下走的时候, 遇到null或者遇到其中一个node就返回该node.
  • 向上走的时候, 通过左右子树在该层的返回值,
    1. 若2个树都返回有效值, 说明在两侧各自找到一个node, 所以该层的root即为2个node的LCA.
    2. 若只有一个找到, 说明在同一个subtree, 即返回该node., 就返回找到的这个node. 注意这个也许是一个小的subtree, 所以找到一个node并不说明该小subtree包含2个node于同一侧.因为若2个在同一侧, 那么返回该node肯定是2个node的LCA; 若在该subtree实际只包含找到的这个node, 而另一个node在另一个subtree里面,那么这次返回可以在另一个node找到的返回合并起来, 返回root, 即1的情况.
    3. 若2个都是null, 就说明该root的左右子树都不包含p,q.

• 代码如下:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
      return null;
    }
    //if (root.val == p.val || root.val == q.val) {  // 不是比较值, 而是比较reference!
    //  return root;
    //}
    if (root == p || root == q) {
      return root;
    }

    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);
    if (l != null && r != null)  return root;
    return l != null ? l : r;
}

然后看LCA of BST

• 注意Binary Search Tree的严格性质:
  1. 左儿子小, 右儿子大.
  2. 所有node的值不一样.
  3. 同一个in-order可以排列成不同的BST.

解法1: 和LCA of Binary Tree类似的recursion

• 之前误打误撞的比较val直接AC了.
• 只要把上面代码里的判断root和p/q, 改为比较val即可.
• 当然这样是很慢的, 因为没有使用BST的顺序性质. 从而没有prune.

解法2: 利用BST的性质的recursion

• LCA分3种情况:

  1. 若root大于p,q最大的, 那么LCA肯定在root左子树.
  2. 若root小于p,q最小的, 那么LCA在root的右子树.
  3. 若$$p \le root \le q$$, 则root即为LCA.

• 代码如下:

public TreeNode lowestCommonAncestorRecur(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
      return null;
    }
    if (root.val < Math.min(p.val, q.val)) {
      return lowestCommonAncestorRecur(root.right, p, q);
    }
    else if (root.val > Math.max(p.val, q.val)){
      return lowestCommonAncestorRecur(root.left, p, q);
    }
    return root;
}

解法3: 将上面的recursion改写为iteration, 而且也是最快的!

• 由于上面的recursion是tail recursion, 所以很好写成iteration. (若不是尾递归, 则要用stack/queue来iterationize)
• 代码如下

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (true) {
      if (root.val > p.val && root.val > q.val) {
        root = root.left;
      }
      else if (root.val < p.val && root.val < q.val) {
        root = root.right;
      }
      else {
        return root;
      }
    }
}