題?描述

輸?兩棵?叉樹A ， B ，判斷B 是不是A 的?結構。（ps：我們約定空樹不是任意?個樹的?結構）

假如給定A 為{8,8,7,9,2,#,#,#,#,4,7} ， B 為{8,9,2} ， 2 個樹的結構如下，可以看出B是A 的?結構:

思路及解答

雙重遞歸法（標準解法）

使用兩個遞歸函數：

1. isSubStructure：遍歷樹A的每個節點，尋找與樹B根節點值相同的節點
2. recur：從匹配的節點開始，遞歸比較兩棵樹的對應節點是否相同

public class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 空樹不是任何樹的子結構
        if (A == null || B == null) return false;
        
        // 三種情況滿足一種即可：
        // 1. B是以A為根的子結構
        // 2. B是A左子樹的子結構
        // 3. B是A右子樹的子結構
        return hasSubtree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    
    // 判斷B是否是A的子結構（從當前節點開始）
    private boolean hasSubtree(TreeNode A, TreeNode B) {
        // B已經遍歷完，說明匹配成功
        if (B == null) return true;
        // A遍歷完但B還有節點，或節點值不匹配
        if (A == null || A.val != B.val) return false;
        // 遞歸比較左右子樹
        return hasSubtree(A.left, B.left) && hasSubtree(A.right, B.right);
    }
}

• 時間復雜度?：O(mn)，m和n分別是樹A和樹B的節點數
• ?空間復雜度?：O(m)，遞歸棧的深度最大為樹A的高度

迭代+遞歸混合法

1. 使用迭代法（棧或隊列）遍歷樹A
2. 當找到與樹B根節點值相同的節點時，切換到遞歸比較
3. 結合了迭代和遞歸的優點

public class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(A);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 找到匹配的根節點，開始遞歸比較
            if (node.val == B.val && compareTrees(node, B)) {
                return true;
            }
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        
        return false;
    }
    
    private boolean compareTrees(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return compareTrees(A.left, B.left) && compareTrees(A.right, B.right);
    }
}

• 時間復雜度?：O(mn)
• ?空間復雜度?：O(m)，棧的空間消耗