解題說明
Leaf-Similar Trees
題目描述:給定兩棵二元樹,若兩棵樹的葉節點序列(由左至右)相同,則稱它們為「葉相似」。請判斷給定的兩棵樹是否葉相似。
解題思路:分別對兩棵樹做深度優先搜尋(DFS),收集所有葉節點的值(葉節點定義:無左子節點且無右子節點)。DFS 採用左子樹優先的中序遍歷順序,確保葉節點從左到右被收集。最後比較兩個葉節點序列是否相等即可。實作上可用遞迴或迭代,遞迴版本最為簡潔直觀。
C++ 解法
複雜度分析
時間複雜度:O(n1 + n2) — 需遍歷兩棵樹的所有節點,n1 和 n2 分別為各樹的節點數。
空間複雜度:O(h1 + h2 + L) — 遞迴呼叫堆疊深度為樹高,額外儲存葉節點序列長度 L。
虛擬碼
1. Define dfs(node, leaves): a. If node is null: return b. If node has no children: append node.val to leaves, return c. dfs(node.left, leaves) d. dfs(node.right, leaves) 2. Collect leaves1 from root1 via dfs 3. Collect leaves2 from root2 via dfs 4. Return leaves1 == leaves2
其他解法
迭代 DFS(使用明確堆疊):用 stack 模擬遞迴,遇到葉節點時記錄,避免遞迴過深造成的 stack overflow。對極度不平衡的樹更安全。
生成器惰性比較:用生成器逐一產出葉節點,邊產出邊比對,一旦發現不同立即提早終止,節省不必要的遍歷。
延伸思考
- 如何在不儲存完整葉節點序列的情況下比較(使用惰性迭代器)?
- 如果樹的節點數非常大(百萬級別),迭代 DFS 相比遞迴有何優勢?
- 如何擴展此概念:比較兩棵樹的「第 k 層節點序列」是否相同?