[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)
- 如果
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)$