Leaf-Similar Trees
題目描述
給定兩棵二元樹的根節點 root1 和 root2，判斷它們是否 leaf-similar — 即兩棵樹從左到右的葉節點值序列相同。
輸入: root1 = [3,5,1,6,2,9,8,null,null,7,4]
root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
輸出: true
解釋: 兩棵樹的葉節點序列都是 [6,7,4,9,8]
解題思路
DFS 收集葉子
對 root1 和 root2 各做一次 DFS，遇到葉節點就將 node.val 加入對應的列表
辨識葉節點
判斷條件為 node.left == null 且 node.right == null，兩邊都沒有子節點
比較兩個序列
逐元素比較兩個葉子列表，長度和每個位置的值都相同才回傳 true
程式碼
C#
public class Solution {
public bool LeafSimilar(TreeNode root1, TreeNode root2) {
var leaves1 = new List<int>();
var leaves2 = new List<int>();
CollectLeaves(root1, leaves1);
CollectLeaves(root2, leaves2);
return leaves1.SequenceEqual(leaves2);
}
private void CollectLeaves(TreeNode node, List<int> leaves) {
if (node == null) return;
if (node.left == null && node.right == null) {
leaves.Add(node.val); // 葉節點
return;
}
CollectLeaves(node.left, leaves);
CollectLeaves(node.right, leaves);
}
}TypeScript
function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
const leaves1: number[] = [];
const leaves2: number[] = [];
collectLeaves(root1, leaves1);
collectLeaves(root2, leaves2);
return leaves1.length === leaves2.length &&
leaves1.every((v, i) => v === leaves2[i]);
}
function collectLeaves(node: TreeNode | null, leaves: number[]): void {
if (!node) return;
if (!node.left && !node.right) {
leaves.push(node.val); // 葉節點
return;
}
collectLeaves(node.left, leaves);
collectLeaves(node.right, leaves);
}Python
def leafSimilar(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def collect_leaves(node, leaves):
if not node:
return
if not node.left and not node.right:
leaves.append(node.val) # 葉節點
return
collect_leaves(node.left, leaves)
collect_leaves(node.right, leaves)
leaves1, leaves2 = [], []
collect_leaves(root1, leaves1)
collect_leaves(root2, leaves2)
return leaves1 == leaves2複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n1 + n2) | O(n1 + n2) |
n1, n2 分別是兩棵樹的節點數。Time O(n1 + n2) 是因為兩棵樹各遍歷一次、每個節點做常數操作。Space O(n1 + n2) 是因為兩個葉子列表最多各存 n/2 個葉節點（完全二元樹），加上遞迴 call stack 深度 O(h)。
邊界情況
- 兩棵都只有根節點：根節點本身就是葉子，比較兩個根的值即可
- 一棵樹的葉子較多：列表長度不同直接回傳 false，不需逐元素比較
- 值相同但順序不同：如一棵葉子序列
[1,2]另一棵[2,1]，回傳 false（順序必須一致）
圖解
圖表展示了兩棵結構不同的樹，各自用 DFS 從左到右收集葉子。兩棵樹的葉子序列都是 [6,7,4,9,8]，逐元素比對完全相同，所以回傳 true。
進階觀點
💡面試追問
Q: 如何用 Generator 優化空間？
A: Python 用 yield 讓 DFS 每找到一個葉子就暫停回傳，不需要一次收集所有葉子。同時遍歷兩個 generator，逐個比較葉子值，遇到不同立即回傳 false。空間從 O(n) 降到 O(h)（只需維護 call stack）。
Q: iterative DFS 如何實作？ A: 用顯式 Stack 取代遞迴。每次 pop 一個節點，如果是葉子就回傳值；否則先 push 右子再 push 左子（確保左子先被處理，維持從左到右的順序）。
變體題：LC 100 Same Tree（結構和值都相同）、LC 101 Symmetric Tree（鏡像對稱）。
理解測驗
🤔 怎麼判斷一個節點是葉節點？
🤔 兩棵結構完全不同的樹可能是 leaf-similar 嗎？