022 · Subtree of Another Tree

algorithm

Published

May 26, 2026

Problem

给定两棵二叉树的根节点 root 和 subRoot。

请判断 subRoot 是否是 root 的一棵子树。

一棵树是另一棵树的子树，意思是：在 root 中可以找到某个节点，从这个节点开始往下的整棵树，和 subRoot 完全相同。

完全相同需要同时满足：

例如，下面这棵 subRoot 是 root 的子树：

root:
        3
       / \
      4   5
     / \
    1   2

subRoot:
      4
     / \
    1   2

因为从 root 中值为 4 的节点开始，下面的结构和值都和 subRoot 一样。

下面这种情况则不是子树：

虽然 root 中也有一个值为 4 的节点，并且下面有 1 和 2，但这个 2 下面还多了一个节点 0，所以整棵树不完全相同。

示例 1

Input:  root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

解释：root 中以节点 4 为根的子树，和 subRoot 完全相同。

示例 2

Input:  root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

解释：root 中看起来有一棵以 4 为根的相似子树，但它的节点 2 下面多了一个节点 0，所以不是完全相同的子树。

示例 3

Input:  root = [1,1], subRoot = [1]
Output: true

解释：root 中的叶子节点 1 本身就可以看作一棵和 subRoot 相同的子树。