572. 另一棵树的子树
题目描述
输入两棵二叉树的根节点 root 和 subRoot，均用层序数组表示，null 表示空位。
以 root 中某个节点为根、连同它的全部后代组成的树，称为 root 的一棵子树；root 整棵树也算它自己的子树。
判断 root 中是否存在一棵子树，其形状与 subRoot 完全一致，并且对应位置的节点值都相等。存在返回 true，否则返回 false。
示例 1
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
解释：以值为 4 的节点为根的子树正好是 [4,1,2]。
示例 2
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
解释：值为 4 的节点下面还挂着节点 0，整棵子树与 subRoot 不一致。
数据范围
root的节点数在[1, 2000]范围内。subRoot的节点数在[1, 1000]范围内。-10^4 <= root.val <= 10^4-10^4 <= subRoot.val <= 10^4
解题思路：递归逐点匹配
先写一个 same(a, b) 判断两棵树是否完全相同：都为空才相同，一空一非空不同，否则比较根值再递归比较左右。然后对 root 的每个节点做候选根：当前节点与 subRoot 相同就找到了，否则到左、右子树里继续找。or 的短路保证找到后立刻停止。
为什么正确
isSubtree(node) 为真，当且仅当 node 本身与 subRoot 相同，或者左、右子树中某一侧包含 subRoot。
复杂度分析
时间 O(n·m)，n、m 为两棵树的节点数（最坏每个候选根都比较 m 次）；空间 O(h)，为递归深度。
易错点
子树必须包含该节点的全部后代。示例 2 中 4 下面的 2 还挂着 0，所以 [4,1,2] 不是它的子树。只比较“开头一样”或只比较值序列都会出错。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def same(a, b):
if not a or not b:
return a is b
return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
if not root:
return False
return same(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)class Solution {
boolean same(TreeNode a, TreeNode b) {
if (a == null || b == null)
return a == b;
return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null)
return false;
return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
}class Solution {
public:
bool same(TreeNode* a, TreeNode* b) {
if (!a || !b)
return a == b;
return a->val == b->val && same(a->left, b->left) && same(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root)
return false;
return same(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
var same func(a, b *TreeNode) bool
same = func(a, b *TreeNode) bool {
if a == nil || b == nil {
return a == b
}
return a.Val == b.Val && same(a.Left, b.Left) && same(a.Right, b.Right)
}
if root == nil {
return false
}
return same(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}var isSubtree = function(root, subRoot) {
const same = (a, b) => {
if (!a || !b)
return a === b;
return a.val === b.val && same(a.left, b.left) && same(a.right, b.right);
};
if (!root)
return false;
return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
const same = (a: TreeNode | null, b: TreeNode | null): boolean => {
if (!a || !b)
return a === b;
return a.val === b.val && same(a.left, b.left) && same(a.right, b.right);
};
if (!root)
return false;
return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}其他解法
递归逐点匹配代码短、不占额外数组，但最坏 O(m·n)；序列化 + KMP 把树匹配转成串匹配，最坏也是线性。
解法 2：先序序列 + KMP 时间 O(m + n)，空间 O(m + n)
用先序遍历把两棵树各自序列化成数组，空子树也写入一个特殊标记。加入空标记后，序列唯一确定一棵树，且一棵子树的序列是原树序列中的一段连续片段。于是问题变成在 root 的序列中查找 subRoot 的序列，用 KMP 的前缀函数做线性匹配。m、n 为两棵树的节点数。
最坏情况下是线性时间，不会退化成 O(m·n)。代价是要额外存两个序列，并且必须写入空标记才能保证匹配正确。
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
NIL = 1 << 30
def serialize(node, out):
if not node:
out.append(NIL)
return
out.append(node.val)
serialize(node.left, out)
serialize(node.right, out)
text, pat = [], []
serialize(root, text)
serialize(subRoot, pat)
fail = [0] * len(pat)
k = 0
for i in range(1, len(pat)):
while k > 0 and pat[i] != pat[k]:
k = fail[k - 1]
if pat[i] == pat[k]:
k += 1
fail[i] = k
k = 0
for x in text:
while k > 0 and x != pat[k]:
k = fail[k - 1]
if x == pat[k]:
k += 1
if k == len(pat):
return True
return Falseclass Solution {
static final int NIL = 1 << 30;
void serialize(TreeNode node, List<Integer> out) {
if (node == null) {
out.add(NIL);
return;
}
out.add(node.val);
serialize(node.left, out);
serialize(node.right, out);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
List<Integer> text = new ArrayList<>(), pat = new ArrayList<>();
serialize(root, text);
serialize(subRoot, pat);
int p = pat.size();
int[] fail = new int[p];
for (int i = 1, k = 0; i < p; i++) {
while (k > 0 && !pat.get(i).equals(pat.get(k))) k = fail[k - 1];
if (pat.get(i).equals(pat.get(k))) k++;
fail[i] = k;
}
int k = 0;
for (int x : text) {
while (k > 0 && x != pat.get(k)) k = fail[k - 1];
if (x == pat.get(k)) k++;
if (k == p) return true;
}
return false;
}
}class Solution {
static constexpr int NIL = 1 << 30;
void serialize(TreeNode* node, vector<int>& out) {
if (!node) {
out.push_back(int(NIL));
return;
}
out.push_back(node->val);
serialize(node->left, out);
serialize(node->right, out);
}
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
vector<int> text, pat;
serialize(root, text);
serialize(subRoot, pat);
int p = pat.size();
vector<int> fail(p, 0);
for (int i = 1, k = 0; i < p; i++) {
while (k > 0 && pat[i] != pat[k]) k = fail[k - 1];
if (pat[i] == pat[k]) k++;
fail[i] = k;
}
int k = 0;
for (int x : text) {
while (k > 0 && x != pat[k]) k = fail[k - 1];
if (x == pat[k]) k++;
if (k == p) return true;
}
return false;
}
};func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
const NIL = 1 << 30
var serialize func(node *TreeNode, out *[]int)
serialize = func(node *TreeNode, out *[]int) {
if node == nil {
*out = append(*out, NIL)
return
}
*out = append(*out, node.Val)
serialize(node.Left, out)
serialize(node.Right, out)
}
text, pat := []int{}, []int{}
serialize(root, &text)
serialize(subRoot, &pat)
p := len(pat)
fail := make([]int, p)
for i, k := 1, 0; i < p; i++ {
for k > 0 && pat[i] != pat[k] {
k = fail[k-1]
}
if pat[i] == pat[k] {
k++
}
fail[i] = k
}
k := 0
for _, x := range text {
for k > 0 && x != pat[k] {
k = fail[k-1]
}
if x == pat[k] {
k++
}
if k == p {
return true
}
}
return false
}var isSubtree = function(root, subRoot) {
const NIL = 1 << 30;
const serialize = (node, out) => {
if (!node) {
out.push(NIL);
return;
}
out.push(node.val);
serialize(node.left, out);
serialize(node.right, out);
};
const text = [], pat = [];
serialize(root, text);
serialize(subRoot, pat);
const p = pat.length;
const fail = new Array(p).fill(0);
for (let i = 1, k = 0; i < p; i++) {
while (k > 0 && pat[i] !== pat[k]) k = fail[k - 1];
if (pat[i] === pat[k]) k++;
fail[i] = k;
}
let k = 0;
for (const x of text) {
while (k > 0 && x !== pat[k]) k = fail[k - 1];
if (x === pat[k]) k++;
if (k === p) return true;
}
return false;
};function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
const NIL = 1 << 30;
const serialize = (node: TreeNode | null, out: number[]): void => {
if (!node) {
out.push(NIL);
return;
}
out.push(node.val);
serialize(node.left, out);
serialize(node.right, out);
};
const text: number[] = [], pat: number[] = [];
serialize(root, text);
serialize(subRoot, pat);
const p = pat.length;
const fail = new Array(p).fill(0);
for (let i = 1, k = 0; i < p; i++) {
while (k > 0 && pat[i] !== pat[k]) k = fail[k - 1];
if (pat[i] === pat[k]) k++;
fail[i] = k;
}
let k = 0;
for (const x of text) {
while (k > 0 && x !== pat[k]) k = fail[k - 1];
if (x === pat[k]) k++;
if (k === p) return true;
}
return false;
}