[LC256] Lowest Common Ancestor

Thursday, January 10, 2019

这道算法题来自 LeetCode #236:在二叉树中找到两个节点的最近公共祖先(LCA)。使用了 JavaScript 实现。

最近公共祖先

按照 Wikipedia 对最近公共祖先的定义:

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

lowest common ancestor for two green nodes
  • 如果 root 为空,则没有找到 pq,直接返回 null 即可
  • 如果 root 恰好是 p 或者 q,则返回它们自身即可
  • 如果 root.leftroot.right 分别找到了 pq,则说明两个节点分别向上移动时会在 root 结点处首次相遇,此时返回 root 即 LCA
  • 如果 root.leftroot.right 的结果只有一个非空,假设这个结果为 node,说明在 root.left 子树或者 root.right 子树找到了 p 或者 q,此时 node 要么是 p 要么是 q, 也可能说明 node 本身就是 LCA。无论是哪种情况,只需返回 node 即可
function lowestCommonAncestor(root, p, q) {
  if (root === null) {
    return null
  }
  
  if (root === p || root === q) {
    return root
  }
  
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  
  if (left !== null && right !== null) {
    return root
  }
  
  return left ? left : right
}

复杂度分析

对于有 N 个结点的二叉树,

  • 时间复杂度:最坏的情况下,每个结点都要遍历一次,所以时间复杂度为 $O(N)$
  • 空间复杂度:最坏的情况下,这棵二叉树是一个线性链表,这样递归函数就需要调用 N 次,所以空间复杂度为 $O(N)$