Key Insight: 最深的葉子可能只有一個，那麼它就是答案。如果最深的葉子有多個，那麼答案就是所有最深葉子的 LCA。
- If the left and right subtree have the same depth, then the current node is the LCA of the deepest nodes.
// Answer = root
root
/ \
/ \
/ \
/ \
L R- If the left subtree is deeper, then the LCA of the deepest nodes is in the left subtree. If the right subtree is deeper, then the LCA of the deepest nodes is in the right subtree.
// Answer = L
root
/ \
/ R
/
/
L So we have to know two key information at each node:
- The depth or height from subtree.
- The LCA from subtree.
We recursively calculate the depth of each node, and return the depth and LCA of the deepest nodes. We don't need to compute the max depth separately. Here's why:
- During the postorder traversal, as we bubble up from leaves, we know the depth of each subtree.
- We can compare left and right depth at each node, it find the max depth naturally.
So our DFS function can simultaneously:
- Compute the deepest depth of each subtree.
- Identify the LCA of all nodes at that deepest depth.
The LCA of all the deepest nodes lies in the subtree where the left and right depth are the same.
dfs(0) = 2
dfs(1) = 2 // we take this as result
dfs(3) = 1
0
/ \
1 3
\
2
dfs(0) = 0
dfs(1) = 2
dfs(3) = 2
// Since dfs(left) == dfs(right), we return root = 0 as result
0
/ \
1 3
\ / \
2 7 8
// return 0
10
/ \
9 0
/ \
1 3
\ / \
2 7 8
// return 0分类讨论：设子树的根节点为
node，node的左子树的高度为leftHeight，node的右子树的高度为rightHeight。
- 如果
leftHeight > rightHeight，那么子树的高度为leftHeight + 1，lca是左子树的lca。- 如果
leftHeight < rightHeight，那么子树的高度为rightHeight + 1，lca是右子树的lca。- 如果
leftHeight = rightHeight，那么子树的高度为leftHeight + 1，lca就是node。
fun subtreeWithAllDeepest(root: TreeNode?): TreeNode? {
return dfs(root).second
}
private fun dfs(root: TreeNode?): Pair<Int, TreeNode?> {
if (root == null) return 0 to null
val (leftDepth, leftLca) = dfs(root.left)
val (rightDepth, rightLca) = dfs(root.right)
return if (leftDepth == rightDepth) {
leftDepth + 1 to root
} else {
if (leftDepth > rightDepth) {
leftDepth + 1 to leftLca
} else {
rightDepth + 1 to rightLca
}
}
} A
/ \
B C
/ \
D E
dfs(A) = 3 to B
dfs(B) = 2 to B
dfs(D) = 1 to D
dfs(null) = 0 to null
dfs(null) = 0 to null
dfs(E) = 1 to E
...
dfs(C) = 1 to C
...Or we can just calculate the depth in top-down manner, and then find the LCA of the deepest nodes.
- If both left and right depth are the same, then this node is the LCA of the deepest nodes.
- Otherwise, if left or right child has deeper depth, then the answer is that child.
private var maxDepth = 0
private var answer: TreeNode? = null
fun subtreeWithAllDeepest(root: TreeNode?): TreeNode? {
dfs(root, 0)
return answer
}
private fun dfs(root: TreeNode?, depth: Int): Int {
if (root == null) return depth
val leftDepth = dfs(root.left, depth + 1)
val rightDepth = dfs(root.right, depth + 1)
val currentDepth = maxOf(leftDepth, rightDepth)
maxDepth = maxOf(maxDepth, currentDepth)
if (leftDepth == maxDepth && rightDepth == maxDepth) {
answer = root
}
return currentDepth
} A
/ \
B C
/ \
D E
dfs(A, 0)
dfs(B, 1) = 3
dfs(D, 2) = 3
dfs(null, 3) = 3
dfs(null, 3) = 3
currentDepth = 3
maxDepth = 3
answer = D
return 3
dfs(null, 2) = 2
currentDepth = 3
maxDepth = 3
return 3
dfs(C, 1) = 3
dfs(null, 2) = 2
dfs(E, 2) = 3
dfs(null, 3) = 3
dfs(null, 3) = 3
currentDepth = 3
maxDepth = 3
answer = B
return 3
currentDepth = 3
maxDepth = 3
return 3
currentDepth = 3
answer = A
return 3We can traverse the tree level by level, then find the LCA of the deepest nodes, but there might be lots of nodes at the same depth, we just pick the leftmost and rightmost node, and find the LCA of two.
fun subtreeWithAllDeepest(root: TreeNode?): TreeNode? {
if (root == null) return null
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
var leftmost: TreeNode? = null
var rightmost: TreeNode? = null
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val node = queue.removeFirst()
if (i == 0) {
leftmost = node
}
// Pitfall: Not "else if", think size == 1
if (i == size - 1) {
rightmost = node
}
if (node.left != null) queue.addLast(node.left)
if (node.right != null) queue.addLast(node.right)
}
}
return lca(root, leftmost, rightmost)
}
// The implementation of LCA, please refer to [236. Lowest Common Ancestor of a Binary Tree](../leetcode/236.lowest-common-ancestor-of-a-binary-tree.md)I explicitly collect all leaf nodes, find the maximum depth, and then find the LCA of all leaf nodes at the maximum depth.
Correct Idea!! But we don’t need to explicitly collect all deepest leaves, then find their LCA. Instead, you can compute LCA during the same DFS traversal that returns the depth and subtree root at that depth.
When solving recursively, we don't need to actual leaf nodes, we just need to know:
- The depth of the deepest node in the subtree.
- The LCA of the deepest nodes in the subtree.
So instead of thinking:
"Let me collect all the deepest nodes, and then call another function to LCA them".
Think:
"Let me walk bottom-up - at each node, I just need to know what's deeper: left or right."
Then:
- If left and right have same depth, this node is the LCA.
- If not, deeper side carries the LCA upward.
| Old mindset | New mindset (recursion-friendly) |
|---|---|
| Gather data first, then post-process | Compute and bubble up the answer during traversal |
| Multiple passes (find leaves → LCA) | One-pass DFS that carries necessary info (depth + node) |
| Think in terms of leaf nodes | Think in terms of subtree properties at each recursion |
| Focus on what nodes are involved | Focus on what to return from each subtree |