572. Subtree of Another Tree

──────────────────────────────────────────────────────────────────────

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

思路

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

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

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

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

解題方向

# 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（本題的內層）、297. Serialize and Deserialize Binary Tree（上面說的序列化解法會用到）、652. Find Duplicate Subtrees（同樣靠序列化子樹來比對）。整理見 Tree 遍歷模板。

複雜度

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

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