236. 二叉树的最近公共祖先 🟨
题目
leetcode 中等
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例：
root = [3,5,1,6,2,0,8,null,null,7,4],
输入：p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
输入：p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
题解
方法：递归
解题思路
我们要找节点 p 和 q 的最近公共祖先。从根节点往下找，如果一个节点的左子树包含了 p，右子树包含了 q（或者反过来），那么这个节点一定就是它们的最近公共祖先。
我们可以通过 后序遍历（自底向上） 将寻找的结果一层层向上传递：
- 终止条件：
- 越过叶子节点，返回 null。
- 如果当前节点等于 p 或 q，说明找到了目标节点，直接返回当前节点。
- 递归工作：
- 递归搜索左子树，返回值记为 left。
- 递归搜索右子树，返回值记为 right。
- 根据返回值判断：
- 情况 1：如果 left 和 right 都不为空，说明 p 和 q 分别在当前节点的两侧，当前节点就是我们要找的最近公共祖先，返回 root。
- 情况 2：如果 left 为空，right 不为空，说明 p 和 q 都不在左子树，直接返回 right。
- 情况 3：如果 right 为空，left 不为空，同理返回 left。
- 情况 4：如果 left 和 right 都为空，说明当前节点的左右子树都没有 p 和 q，返回 null。
复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
js
function lowestCommonAncestor(root, p, q) {
console.log('♻️ root', root ? root.val : null)
// 1. 递归终止条件
// 如果走到空节点，或者找到了 p 或 q，直接返回
if (root === null || root === p || root === q) {
console.log('🛑 停止', root ? root.val : null)
return root
}
// 2. 递归遍历左右子树
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
// 3. 处理返回值
// 如果 left 和 right 都非空，说明 p 和 q 分布在 root 的两侧，root 就是最近公共祖先
if (left !== null && right !== null) {
console.log('找到最近公共祖先', root.val)
return root
}
// 如果只有一个非空，说明 p 和 q 在同一侧，返回非空的那个节点（它或者是 p/q，或者是最近公共祖先）
// 如果都为空，返回 null
const result = left !== null ? left : right
console.log('返回', result)
return result
}
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}
const tree = new TreeNode(3)
tree.left = new TreeNode(
5,
new TreeNode(6),
new TreeNode(2, new TreeNode(7), new TreeNode(4)),
)
tree.right = new TreeNode(1, new TreeNode(0), new TreeNode(8))
console.log('🌰', lowestCommonAncestor(tree, tree.left, tree.right.right)) // 5 和 8 的最近公共祖先是 3
console.log('--------------')
console.log('🌰', lowestCommonAncestor(tree, tree.left, tree.left.right.right)) // 5 和 4 的最近公共祖先是 5执行结果
♻️ root 3
♻️ root 5
🛑 停止 5
♻️ root 1
♻️ root 0
♻️ root null
🛑 停止 null
♻️ root null
🛑 停止 null
返回 null
♻️ root 8
🛑 停止 8
返回 TreeNode { val: 8, left: null, right: null }
找到最近公共祖先 3
🌰 TreeNode {
val: 3,
left: TreeNode {
val: 5,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode {
val: 2,
left: TreeNode { val: 7, left: null, right: null },
right: TreeNode { val: 4, left: null, right: null }
}
},
right: TreeNode {
val: 1,
left: TreeNode { val: 0, left: null, right: null },
right: TreeNode { val: 8, left: null, right: null }
}
}
--------------
♻️ root 3
♻️ root 5
🛑 停止 5
♻️ root 1
♻️ root 0
♻️ root null
🛑 停止 null
♻️ root null
🛑 停止 null
返回 null
♻️ root 8
♻️ root null
🛑 停止 null
♻️ root null
🛑 停止 null
返回 null
返回 null
返回 TreeNode {
val: 5,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode {
val: 2,
left: TreeNode { val: 7, left: null, right: null },
right: TreeNode { val: 4, left: null, right: null }
}
}
🌰 TreeNode {
val: 5,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode {
val: 2,
left: TreeNode { val: 7, left: null, right: null },
right: TreeNode { val: 4, left: null, right: null }
}
}
方法：迭代
解题思路
- 从根节点开始遍历二叉树（DFS或BFS均可），用一个 Map 记录每个节点的父节点（Map<当前节点, 父节点>）。
- 直到把 p 和 q 的父节点都记录下来。
- 从节点 p 开始，利用 Map 不断往上跳，把 p 的所有祖先节点记录到一个 Set 中。
- 从节点 q 开始，利用 Map 不断往上跳，每次跳都检查当前节点是否在刚刚的 Set 中。第一个在 Set 中出现的节点，就是最近公共祖先！
复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
js
function lowestCommonAncestor(root, p, q) {
// 使用 Map 记录每个节点的父节点：key 为当前节点，value 为父节点
const parentMap = new Map()
const queue = [root]
parentMap.set(root, null) // 根节点没有父节点
// BFS 遍历，直到 p 和 q 的父节点都被我们记录下来
while (!parentMap.has(p) || !parentMap.has(q)) {
const node = queue.shift()
if (node.left) {
parentMap.set(node.left, node)
queue.push(node.left)
}
if (node.right) {
parentMap.set(node.right, node)
queue.push(node.right)
}
console.log(
'queue',
queue.map(n => n.val),
)
console.log(
'parentMap',
JSON.stringify(
Array.from(parentMap.entries()).map(([node, parent]) => [
node.val,
parent ? parent.val : null,
]),
),
)
}
// 记录 p 的所有祖先
const ancestors = new Set()
let current = p
while (current !== null) {
console.log('p current', current.val)
ancestors.add(current)
current = parentMap.get(current) // 向上找父节点
console.log(
'ancestors',
Array.from(ancestors).map(node => node.val),
)
}
// 从 q 开始向上找，遇到第一个存在于 ancestors 集合中的节点就是 LCA
current = q
while (!ancestors.has(current)) {
console.log('q current', current.val)
current = parentMap.get(current)
console.log(
'ancestors',
Array.from(ancestors).map(node => node.val),
)
}
return current
}
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}
const tree = new TreeNode(3)
tree.left = new TreeNode(
5,
new TreeNode(6),
new TreeNode(2, new TreeNode(7), new TreeNode(4)),
)
tree.right = new TreeNode(1, new TreeNode(0), new TreeNode(8))
console.log('🌰', lowestCommonAncestor(tree, tree.left, tree.right.right)) // 5 和 8 的最近公共祖先是 3
console.log('--------------')
console.log('🌰', lowestCommonAncestor(tree, tree.left, tree.left.right.right)) // 5 和 4 的最近公共祖先是 5执行结果
queue [ 5, 1 ]
parentMap [[3,null],[5,3],[1,3]]
queue [ 1, 6, 2 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5]]
queue [ 6, 2, 0, 8 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5],[0,1],[8,1]]
p current 5
ancestors [ 5 ]
p current 3
ancestors [ 5, 3 ]
q current 8
ancestors [ 5, 3 ]
q current 1
ancestors [ 5, 3 ]
🌰 TreeNode {
val: 3,
left: TreeNode {
val: 5,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode {
val: 2,
left: TreeNode { val: 7, left: null, right: null },
right: TreeNode { val: 4, left: null, right: null }
}
},
right: TreeNode {
val: 1,
left: TreeNode { val: 0, left: null, right: null },
right: TreeNode { val: 8, left: null, right: null }
}
}
--------------
queue [ 5, 1 ]
parentMap [[3,null],[5,3],[1,3]]
queue [ 1, 6, 2 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5]]
queue [ 6, 2, 0, 8 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5],[0,1],[8,1]]
queue [ 2, 0, 8 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5],[0,1],[8,1]]
queue [ 0, 8, 7, 4 ]
parentMap [[3,null],[5,3],[1,3],[6,5],[2,5],[0,1],[8,1],[7,2],[4,2]]
p current 5
ancestors [ 5 ]
p current 3
ancestors [ 5, 3 ]
q current 4
ancestors [ 5, 3 ]
q current 2
ancestors [ 5, 3 ]
🌰 TreeNode {
val: 5,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode {
val: 2,
left: TreeNode { val: 7, left: null, right: null },
right: TreeNode { val: 4, left: null, right: null }
}
}