一、題目解析

題目描述

給定兩棵二叉樹root和subRoot，判斷root中是否存在一棵子樹，其結構和節點值與subRoot完全相同。

示例說明

• 示例1：
  root = [3,4,5,1,2]，subRoot = [4,1,2]
  返回true，因為root的左子樹與subRoot完全相同。

• 示例2：
  root = [3,4,5,1,2,null,null,null,null,0]，subRoot = [4,1,2]
  返回false，雖然root存在節點值為4、1、2的路徑，但結構與subRoot不同。

核心難點

1. 如何高效遍歷主樹，找到可能與子樹匹配的起始節點？
2. 如何精確判斷兩棵樹是否完全相同，避免結構或值的差異？

二、遞歸解法：深度優先搜索

核心思路

1. 遞歸遍歷主樹：對主樹的每個節點，檢查以該節點為根的子樹是否與目標子樹相同。
2. 遞歸判斷子樹是否相同：同時遍歷兩棵樹的對應節點，確保結構和值完全一致。

代碼實現

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {return bfs(root,subRoot);}public boolean bfs(TreeNode root, TreeNode subRoot){if(root == null){return false;}return check(root,subRoot) || bfs(root.left,subRoot) || bfs(root.right,subRoot);}public boolean check(TreeNode root, TreeNode subRoot){if(root == null && subRoot == null){return true;}if(root == null || subRoot == null || root.val != subRoot.val){return false;}return check(root.left,subRoot.left) && check(root.right,subRoot.right);}
}

代碼解析

1. 主方法 isSubtree：
   調用bfs方法開始遞歸遍歷主樹。

2. 遞歸遍歷方法 bfs：

   • 終止條件：若主樹為空，返回false。
   • 檢查當前節點：調用check方法判斷以當前節點為根的子樹是否與目標子樹相同。
   • 遞歸搜索左右子樹：只要在任一子樹中找到匹配，立即返回true。

3. 子樹比較方法 check：

   • 終止條件：若兩節點均為空，返回true；若僅一者為空或值不同，返回false。
   • 遞歸比較：遞歸檢查左右子樹是否完全相同。

三、迭代解法：雙端隊列層序遍歷

核心思路

1. 層序遍歷主樹：使用雙端隊列按層遍歷主樹的每個節點。
2. 檢查子樹是否相同：對每個節點，使用另一個雙端隊列同步比較其與目標子樹的結構和值。

代碼實現

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {Deque<TreeNode> cur = new LinkedList<>();if (subRoot == null) return true;  if (root == null) return false;   TreeNode tempRoot = root;cur.offer(tempRoot);while(!cur.isEmpty()){tempRoot = cur.pollFirst();if(isSameTree(tempRoot,subRoot)){return true;}if(tempRoot.left != null){cur.offerFirst(tempRoot.left);}if(tempRoot.right != null){cur.offerFirst(tempRoot.right);}}return false;}public boolean isSameTree(TreeNode root, TreeNode subRoot) {Deque<TreeNode> cur = new LinkedList<>();if (root == null && subRoot == null) {return true;}TreeNode tempRoot = root;TreeNode tempSubRoot = subRoot;cur.offerFirst(tempRoot);cur.offerLast(tempSubRoot);while (!cur.isEmpty()) {tempRoot = cur.pollFirst();tempSubRoot = cur.pollLast();if (tempRoot == null && tempSubRoot == null) {continue;}if (tempRoot == null || tempSubRoot == null || tempSubRoot.val != tempRoot.val) {return false;}cur.offerFirst(tempRoot.left);cur.offerFirst(tempRoot.right);cur.offerLast(tempSubRoot.left);cur.offerLast(tempSubRoot.right);}return true;}
}

代碼解析

1. 主方法 isSubtree：

   • 初始化隊列：將主樹根節點入隊。
   • 層序遍歷：每次從隊列取出節點，調用isSameTree檢查是否匹配。
   • 擴展隊列：將當前節點的左右子節點入隊，繼續遍歷。

2. 子樹比較方法 isSameTree：

   • 雙隊列同步遍歷：使用雙端隊列分別存儲主樹和子樹的節點。
   • 節點比較：每次從隊列取出兩個節點，檢查是否結構和值相同，并將其子節點入隊。
   • 入隊策略：主樹節點從隊首入隊，子樹節點從隊尾入隊，確保對應節點同步比較。

四、尋找匹配節點的關鍵邏輯

遞歸法

• 遍歷策略：采用前序遍歷（根→左→右），確保每個節點都被檢查。
• 匹配條件：當且僅當當前節點及其所有后代與子樹完全相同時，返回true。

迭代法

• 遍歷策略：層序遍歷（BFS），按層檢查每個節點。
• 匹配條件：使用雙隊列同步比較，確保每個對應節點的結構和值一致。

對比分析

方法	遍歷方式	時間復雜度	空間復雜度	適用場景
遞歸法	深度優先（DFS）	O(m*n)	O(max(h1,h2))	樹較淺，遞歸棧空間充足
迭代法	廣度優先（BFS）	O(m*n)	O(max(w1,w2))	避免遞歸棧溢出

其中，m和n分別為主樹和子樹的節點數，h為樹的高度，w為樹的最大寬度。

五、常見誤區與邊界條件

1. 空樹處理

• 子樹為空：題目規定空樹是任何樹的子樹，因此直接返回true。
• 主樹為空：若主樹為空，僅當子樹也為空時返回true，否則返回false。

2. 結構與值的雙重匹配

• 示例：主樹[1,1]，子樹[1]。
  雖然主樹存在節點值為1的子樹，但結構不同（主樹有兩個節點），因此返回false。

3. 部分路徑匹配問題

• 示例：主樹[3,4,5,1,2,null,null,null,null,0]，子樹[4,1,2]。
  主樹的左子樹路徑為4→1→2，但2的右子節點存在0，與子樹結構不符，故返回false。

六、總結

核心算法思路

1. 遍歷主樹：遞歸或迭代方式遍歷每個節點。
2. 檢查子樹：對每個節點，遞歸或迭代比較其與目標子樹的結構和值。

代碼優化建議

1. 遞歸法：簡潔直觀，但可能導致棧溢出，適用于樹高較小的場景。
2. 迭代法：避免棧溢出，但代碼復雜度較高，需維護雙隊列同步遍歷。

關鍵技巧

• 雙隊列同步遍歷：確保主樹和子樹的對應節點被正確比較。
• 層序遍歷：通過隊列按層處理節點，適合大規模數據。

理解這兩種解法的核心邏輯后，可靈活應對類似的樹結構匹配問題，如判斷樹的子結構、樹的鏡像等變體。