【LetMeFly】572.另一棵树的子树：深搜+广搜（n^2做法就能过，也有复杂度耕地的算法）

力扣题目链接：https://leetcode.cn/problems/subtree-of-another-tree/

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

 

示例 1：

leetcode.com%2Fuploads%2F2021%2F04%2F28%2Fsubtree1-tree.jpg&pos_id=img-NwWwQRoc-1722869538024%29" />

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

示例 2：

leetcode.com%2Fuploads%2F2021%2F04%2F28%2Fsubtree2-tree.jpg&pos_id=img-BUdtugC2-1722869543533%29" />

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

 

提示：

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

解题方法：深搜+广搜（硬匹配）

如何判断两个树是否相同呢？

我们可以写一个函数isSame(rootA, rootB)来判断以rootA为根的树是否和以rootB为根的树相同。

首先如果rootA和rootB中有一个为空，那么他们都要为空才能相等；

否则（都不为空），rootA的值必须和rootB的值相等，并且他们的左子树相等（可递归判断），右子树也相等，两棵树才能相同。

因此，我们可以遍历以root为根的这棵树的每一个节点（深搜和广搜都可，本题解中C++代码以广搜为例，Python代码以深搜为例），判断以每个节点为根的树是否和以subRoot为根的树相同。一旦存在相同的子树，则立即返回true。

• 时间复杂度$O(size(root)\times size(subRoot))$
• 空间复杂度$O(size(root))$

AC代码

C++

class Solution {
private:bool isSame(TreeNode* a, TreeNode* b) {if (!a || !b) {return a == b;}return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);}
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {queue<TreeNode*> q;q.push(root);while (q.size()) {TreeNode* thisNode = q.front();q.pop();if (isSame(thisNode, subRoot)) {return true;}if (thisNode->left) {q.push(thisNode->left);}if (thisNode->right) {q.push(thisNode->right);}}return false;}
};

Python

# from typing import Optional
# # 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 = rightclass Solution:def isSame(self, a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:if not a or not b:return a == breturn a.val == b.val and self.isSame(a.left, b.left) and self.isSame(a.right, b.right)def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:if not root:return Falseif self.isSame(root, subRoot):return Truereturn self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

解题方法拓展

假设两棵树的节点个数分别为m和n。

上述解题方法中，如果二叉树退化成链，且树中元素几乎全为1，则要比较接近$mn$次。

有没有什么能提升效率的方法呢？其实我们在深搜以root为根的树的时候可以统计一下每个节点距其子树最远叶子节点的距离，只有高度相同的树才有可能相同。这样，每个节点不会被比较多次，我们就将时间复杂度降低到了$O(m)$。（如果$n>m$则不会比完全以subRoot为根节点的树的节点）

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140939018