---
title: "572. Subtree of Another Tree"
url: "https://laigary.com/interview/coding/572-subtree-of-another-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Tree", "Depth-First Search"]
---

# 572. Subtree of Another Tree

[572\. Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)

判斷 `subRoot` 是不是 `root` 的一棵子樹。「子樹」的定義是：`root` 裡的某個節點，連同它底下**全部**的後代，和 `subRoot` 完全相同。

## 思路

關鍵是先把「子樹」的定義讀準：不是「長得像的一部分」，而是**某個節點以下整個都要一模一樣**。一旦這樣理解，題目就拆成兩層：

1. **外層**：走訪 `root` 的每一個節點，把它當成候選的起點
2. **內層**：對每個候選起點，檢查「以它為根的子樹」和 `subRoot` 是否完全相同

而第 2 步正好就是 [100. Same Tree](/interview/coding/100-same-tree)。所以這題不需要新的想法，只是**在 100 外面包一層遍歷**。這種「已知題當子程序」的結構很值得習慣 —— 面試時先說「內層我用判斷兩棵樹相同的函式，外層對每個節點試一次」，比一頭栽進去寫穩得多。

要注意的是**每個候選點都要從頭比對整棵**，不能因為前面比對到一半失敗就跳過那個分支 —— 失敗只代表「以這個節點為根不行」，它的子節點仍然可能是答案。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def isMatch(self, TreeA: TreeNode, TreeB: TreeNode):
        if not TreeA or not TreeB:
            return TreeA == TreeB
        return (TreeA.val == TreeB.val and self.isMatch(TreeA.left, TreeB.left) and self.isMatch(TreeA.right, TreeB.right))

    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if self.isMatch(root, subRoot):
            return True
        if not root:
            return False

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
```

`isMatch` 裡的 `if not TreeA or not TreeB: return TreeA == TreeB` 是個緊湊的寫法，一行處理了兩種情況：

- 兩邊都是 `None` → `None == None` → `True`
- 只有一邊是 `None` → `None == 某個節點` → `False`

比展開成兩個 `if` 短，但可讀性見仁見智；面試時如果覺得對方看不懂，展開寫也完全沒問題。

外層 `isSubtree` 的順序是「**先試自己，再試左右**」，並且用 `or` 短路 —— 左子樹找到就不會再走右子樹。`if not root: return False` 要放在 `isMatch` 之後，因為 `root` 是 `None` 而 `subRoot` 也是 `None` 的情況要先讓 `isMatch` 回 `True`。

## 補充

**這題的複雜度是 $O(m \times n)$，不是 $O(m + n)$**，因為外層每個節點都可能觸發一次完整的內層比對。這也帶出下一個問題：**能不能更快？**

**能。** 一個常見的優化方向是把兩棵樹**序列化成字串**（前序 + 用特殊符號標記空節點），然後問「`subRoot` 的字串是不是 `root` 的字串的子字串」。配上 KMP 這類字串比對演算法就能做到 $O(m + n)$。我沒有用這個角度寫過這題，所以這裡不展開，但值得知道有這條路 —— 面試被追問時說得出方向就夠了。

**相關題**：[100. Same Tree](/interview/coding/100-same-tree)（本題的內層）、[297. Serialize and Deserialize Binary Tree](/interview/coding/297-serialize-and-deserialize-binary-tree)（上面說的序列化解法會用到）、[652. Find Duplicate Subtrees](/interview/coding/652-find-duplicate-subtrees)（同樣靠序列化子樹來比對）。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(m \times n)$ — 外層走 `root` 的 `m` 個節點，每個節點最壞要花 $O(n)$ 比對整棵 `subRoot`
- 空間 $O(h_{root} + h_{sub})$ — 兩層遞迴的堆疊；最壞情況兩棵都退化成鏈，變成 $O(m + n)$

其中 `m` 是 `root` 的節點數、`n` 是 `subRoot` 的節點數。實務上遠比 $O(m \times n)$ 快，因為值不同時第一步就短路了 —— 但最壞情況仍然是這個量級。