What is the most efficient way to check if one tree is a subtree of another?

Use recursive DFS traversal and optional subtree hashing to compare structure and node values efficiently.

Can iterative traversal replace recursion for the subtree check?

Yes, iterative DFS or BFS using a stack or queue can replace recursion and prevent stack overflow in deep trees.

Why do some implementations give false positives?

False positives often occur when only node values are compared without checking the full subtree structure.

How does hashing improve subtree comparison?

Hashing encodes subtree structures and values into a single representation, allowing quick equality checks instead of repeated recursive comparison.

Does this problem pattern involve string matching?

Yes, comparing serialized or hashed subtrees is similar to string matching, making pattern detection efficient.

#572

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。 tree 也可以看做它自身的一棵子树。 …

树深度优先搜索字符串匹配二叉树哈希函数

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

lightbulb

解题思路

方法一：DFS

我们定义一个辅助函数 $\textit{same}(p, q)$ ，用于判断以 $p$ 为根节点的树和以 $q$ 为根节点的树是否相等。如果两棵树的根节点的值相等，并且它们的左子树和右子树也分别相等，那么这两棵树是相等的。

在 $\textit{isSubtree}(\textit{root}, \textit{subRoot})$ 函数中，我们首先判断 $\textit{root}$ 是否为空，如果为空，则返回 $\text{false}$ 。否则，我们判断 $\textit{root}$ 和 $\textit{subRoot}$ 是否相等，如果相等，则返回 $\text{true}$ 。否则，我们递归地判断 $\textit{root}$ 的左子树和右子树是否包含 $\textit{subRoot}$ 。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是树 $root$ 和树 $subRoot$ 的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None or q is None:
                return p is q
            return p.val == q.val and same(p.left, q.left) and same(p.right, q.right)

        if root is None:
            return False
        return (
            same(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

speed

复杂度分析

指标	值
时间	complexity can reach O(m*n) in the worst case for comparing m nodes in root with n nodes in subRoot, but hashing or pruning identical subtrees can reduce comparisons. Space complexity depends on recursion stack depth or storage for subtree hashes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks whether recursion or iterative traversal is preferable for subtree comparison.
question_mark
Checks if null node handling is correctly implemented in the DFS solution.
question_mark
Mentions optimization using subtree serialization or hashing techniques.

warning

常见陷阱

外企场景

error
Failing to check both left and right children for exact match leading to false positives.
error
Confusing a node with identical value as a valid subtree without matching the full structure.
error
Exceeding recursion limits on deeply nested trees without iterative fallback.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine if a tree is a mirror subtree of another, requiring reversed child comparisons.
arrow_right_alt
Count the total number of occurrences where subRoot appears as a subtree within root.
arrow_right_alt
Check if subRoot appears as a subtree in a forest of multiple disconnected trees.

help

常见问题

外企场景

继续练习

#563 二叉树的坡度 #538 把二叉搜索树转换为累加树 #606 根据二叉树创建字符串