題目
#

leetcode 572 - Subtree of Another Tree (題目說明請點連結)

題目簡述
#

判斷一棵樹是否是另一棵樹的子樹。

範例
#

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Explanation: 給定的子樹 [4,1,2] 是主樹 [3,4,5,1,2] 的一部分。

主樹：

graph TD; A[3] B[4] C[5] D[1] E[2] A --> B A --> C B --> D B --> E

子樹：

graph TD; B[4] D[1] E[2] B --> D B --> E

Example 2:

Input: root = [3,4,5,1,2,null,null,0], subRoot = [4,1,2]
Output: false
Explanation: 給定的子樹 [4,1,2] 不是主樹 [3,4,5,1,2,null,null,0] 的一部分。

主樹：

graph TD; A[3] B[4] C[5] D[1] E[2] F[0] A --> B A --> C B --> D B --> E D --> F

子樹：

graph TD; B[4] D[1] E[2] B --> D B --> E

解題思路
#

這題要求我們判斷一個樹是否是另一個樹的子樹。子樹的定義是，樹中的某個節點及其所有後代節點構成的樹。我們可以使用遞迴的方法來檢查每個節點是否與子樹的根節點相同，並進一步檢查其子樹是否相同。

解法
#

遞迴檢查法（Recursive Check Approach）

如果 subRoot 是 null，則它一定是子樹，返回 true
如果 root 是 null，但 subRoot 不是，則不是子樹，返回 false
如果兩棵樹從這個節點開始一樣，返回 true
否則，遞迴檢查左子樹和右子樹

步驟
#

初始化：
- 檢查 subRoot 是否為 null
遞迴檢查：
- 檢查 root 是否為 null
- 檢查兩棵樹是否相同
- 遞迴檢查左子樹和右子樹
返回結果：
- 返回檢查結果

例子說明
#

root = [3,4,5,1,2], subRoot = [4,1,2]

步驟	節點	檢查結果
初始化	-	檢查 subRoot 是否為 null
檢查根節點	3	不同，繼續檢查子樹
檢查左子樹	4	相同，檢查子樹
檢查右子樹	5	不同，返回 false
最終結果	-	返回 true，subRoot 是 root 的子樹

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        // 如果 subRoot 是 null，一定是子樹
        if(subRoot == null) return true;
        // 如果 root 是 null，但 subRoot 不是，那就不是子樹
        if(root == null) return false;
        // 如果兩棵樹從這個節點開始一樣，就直接返回 true
        if(isSametree(root,subRoot)) return true;

         // 否則就繼續往左邊或右邊找
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    // 檢查兩棵樹是否完全一樣（值一樣、結構一樣）
    public boolean isSametree(TreeNode s, TreeNode t)
    {
        if(s == null && t == null) return true;
        else if(s==null || t == null) return false;
        else if(s.val != t.val) return false;

        return isSametree(s.left,t.left) && isSametree(s.right,t.right);

    }
}