[LC256] Lowest Common Ancestor

这道算法题来自 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)

• 如果 root 为空，则没有找到 p 或 q，直接返回 null 即可
• 如果 root 恰好是 p 或者 q，则返回它们自身即可
• 如果 root.left 和 root.right 分别找到了 p 和 q，则说明两个节点分别向上移动时会在 root 结点处首次相遇，此时返回 root 即 LCA
• 如果 root.left 或 root.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)$