在二叉樹操作中，判斷兩棵樹是否相同是一個常見的問題。本文將對比兩種不同的解決方案：遞歸法和遍歷序列對比法，分析它們的優缺點，并探討為何遞歸法是更優的選擇。

問題描述

給定兩棵二叉樹的根節點?p?和?q，判斷它們是否在結構和節點值上完全相同。

方法一：遞歸法

遞歸法的核心思想是逐層比較節點，確保每個節點的值和結構一致。

public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) return true;else if (p == null || q == null) return false;else if (p.val != q.val) return false;return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

分析

1. 正確性：遞歸法直接比較當前節點的值和結構，并遞歸檢查左右子樹。只有當所有對應節點均匹配時，才返回?true。

2. 時間復雜度：O(n)，每個節點僅訪問一次。

3. 空間復雜度：O(h)，其中 h 為樹的高度（遞歸棧的深度）。

方法二：遍歷序列對比法

該方法通過生成兩棵樹的前序、中序和后序遍歷序列，并比較三者是否完全一致。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {List<Integer> arrMiddleP = new ArrayList<Integer>();List<Integer> arrMiddleQ = new ArrayList<Integer>();List<Integer> preP = new ArrayList<Integer>();List<Integer> preQ = new ArrayList<Integer>();List<Integer> afterP = new ArrayList<Integer>();List<Integer> afterQ = new ArrayList<Integer>();middle(p, arrMiddleP);middle(q, arrMiddleQ);pre(p, preP);pre(q, preQ);after(p, afterP);after(q, afterQ);if (arrMiddleP.equals(arrMiddleQ) && preP.equals(preQ)&&(afterP.equals(afterQ))) {return true;}return false;}public void middle(TreeNode x, List<Integer> arrMiddle) {if (x == null) {return;}middle(x.left, arrMiddle);arrMiddle.add(x.val);middle(x.right, arrMiddle);}public void pre(TreeNode x, List<Integer> arrPre) {if (x == null) {return;}arrPre.add(x.val);pre(x.left, arrPre);pre(x.right, arrPre);}public void after(TreeNode x, List<Integer> arrPre) {if (x == null) {return;}after(x.left, arrPre);after(x.right, arrPre);arrPre.add(x.val);}}

分析

1. 思路：如果兩棵樹的前序、中序、后序遍歷結果完全相同，則認為它們相同。

2. 潛在問題：

   • 結構信息丟失：遍歷序列未記錄?null?節點，導致不同結構的樹可能生成相同的遍歷序列。例如：

     • 樹 A：根節點為?1，左子節點為?1。

     • 樹 B：根節點為?1，右子節點為?1。
       兩者的前序、中序、后序結果均為?[1, 1]，但結構不同。

   • 重復值問題：當節點值重復時，遍歷序列無法區分結構差異。

3. 效率：需要三次遍歷，時間和空間復雜度均為 O(n)，效率低于遞歸法。

---

對比與結論

方法	正確性	時間復雜度	空間復雜度	結構敏感性
遞歸法	?	O(n)	O(h)	?
遍歷序列對比法	?	O(n)	O(n)	?

1. 正確性：遞歸法直接比較結構和值，適用于所有情況。遍歷序列法在節點值重復或結構歧義時可能失效。

2. 效率：遞歸法在早期發現不同時可立即返回，而遍歷序列法必須完成所有遍歷。

3. 實現復雜度：遞歸法代碼簡潔，邏輯清晰；遍歷序列法需要額外生成和比較多個序列。

---

為什么遞歸法更優？

• 結構敏感性：遞歸法嚴格檢查每個節點的位置和值，確保結構完全一致。

• 提前終止：一旦發現節點不匹配，遞歸立即終止，避免不必要的遍歷。

• 資源友好：無需存儲遍歷結果，空間復雜度更低。