022 · Subtree of Another Tree

My First Thoughts

看到这道题，很自然会想到前面的 020 · Same Tree。

因为题目问的是：subRoot 是否是 root 的一棵子树。

而“是子树”的意思其实就是：

在 root 里面找到某个节点，从这个节点开始的整棵树，和 subRoot 完全相同。

所以第一反应可以是：

1. 遍历 root 中的每一个节点
2. 对每个节点，都把它当作一棵小树的根
3. 用 isSameTree 判断这棵小树是否和 subRoot 一样

这个方向是对的，而且已经非常接近正解。

可以先写出大概结构：

def isSubtree(root, subRoot):
    def isSameTree(p, q):
        ...

    if isSameTree(root, subRoot):
        return True

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

这段思路表达得很清楚：先看当前位置能不能匹配，如果不能，就去左子树和右子树继续找。

---

Why That Is Not Enough

这里主要差一个递归边界。

题目约束里说：

root 中节点数量至少是 1
subRoot 中节点数量至少是 1

这说明最开始传进来的 root 和 subRoot 都不是空树。

但是递归过程中，我们会继续调用：

isSubtree(root.left, subRoot)
isSubtree(root.right, subRoot)

当一路走到叶子节点下面时，root.left 或 root.right 就会是 None。

所以 isSubtree 里面仍然需要处理：

if root is None:
    return False

这句话的意思是：如果 root 这边已经没有节点了，就不可能在这里找到一个非空的 subRoot。

另外，函数名和参数名最好保持一致，比如统一写成 LeetCode 常见的：

isSubtree(root, subRoot)

---

Final Idea

这道题可以拆成两个递归函数。

第一个函数是已经学过的 isSameTree(p, q)：

判断以 p 和 q 为根节点的两棵树是否完全相同。

它负责比较结构和值：

if p is None and q is None:
    return True

if p is None or q is None:
    return False

if p.val != q.val:
    return False

return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

第二个函数是这道题本身的 isSubtree(root, subRoot)：

判断 root 这棵树里面，是否存在一棵和 subRoot 完全相同的子树。

每到一个 root 节点，都有三种可能：

1. 当前这棵树就和 subRoot 完全相同
2. 答案在 root.left 里面
3. 答案在 root.right 里面

写成代码就是：

return (
    isSameTree(root, subRoot)
    or isSubtree(root.left, subRoot)
    or isSubtree(root.right, subRoot)
)

但在这之前，要先处理 root is None：

if root is None:
    return False

因为 subRoot 按题目约束不是空树，所以空的 root 不可能包含它。

以这个例子为例：

root:
        3
       / \
      4   5
     / \
    1   2

subRoot:
      4
     / \
    1   2

递归过程可以这样看：

isSubtree(3, 4)
├── isSameTree(3, 4) → False
├── isSubtree(4, 4)
│   └── isSameTree(4, 4) → True
└── 不需要再继续看右边

所以最终返回 True。

---

Why It Works

如果 subRoot 是 root 的子树，那么它一定对应 root 里面的某一个节点。

所以只要把 root 的每个节点都当作候选起点检查一次，就不会漏掉答案。

对于每个候选起点：

• 用 isSameTree(root, subRoot) 判断当前位置是否完全匹配
• 如果当前位置不匹配，就继续去左子树找
• 如果左子树也找不到，就继续去右子树找

递归函数 isSubtree(root, subRoot) 的含义很明确：在当前这棵 root 树里，能不能找到一棵和 subRoot 相同的子树。

因为它检查了当前节点、左子树、右子树这三种可能，所以只要答案存在，就一定会返回 True。

---

Code

def isSubtree(root, subRoot):
    def isSameTree(p, q):
        if p is None and q is None:
            return True

        if p is None or q is None:
            return False

        if p.val != q.val:
            return False

        return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

    if root is None:
        return False

    if isSameTree(root, subRoot):
        return True

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

---

Complexity

Time	\(O(n \times m)\) — n 是 root 的节点数，m 是 subRoot 的节点数；最坏情况下，root 的很多节点都要触发一次 isSameTree 比较
Space	\(O(h + k)\) — 递归调用栈来自遍历 root 的高度 h，以及比较 subRoot 时的高度 k，最坏情况下可以到 \(O(n + m)\)

---

Takeaway

这题的核心就是复用 Same Tree。isSameTree 负责判断“当前位置是否完全一样”，isSubtree 负责在 root 里不断移动候选起点。即使题目保证初始输入不是空树，递归走到叶子节点下面时仍然会遇到 None，所以 root is None 这个边界不能省。

---

← Quiz