解題說明
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 層節點序列」是否相同？