572. 另一棵树的子树
572. 另一棵树的子树
🟢 🔖 树
深度优先搜索
二叉树
字符串匹配
哈希函数
🔗 力扣
LeetCode
题目
Given the roots of two binary trees root
and subRoot
, return true
if there is a subtree of root
with the same structure and node values of subRoot
and false
otherwise.
A subtree of a binary tree tree
is a tree that consists of a node in tree
and all of this node's descendants. The tree tree
could also be considered as a subtree of itself.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Constraints:
- The number of nodes in the
root
tree is in the range[1, 2000]
. - The number of nodes in the
subRoot
tree is in the range[1, 1000]
. -10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
题目大意
给定两个非空二叉树 root
和 subRoot
,检验 root
中是否包含和 subRoot
具有相同结构和节点值的子树。root
的一个子树包括 root
的一个节点和这个节点的所有子孙。root
也可以看做它自身的一棵子树。
解题思路
可以使用递归来判断,分为三种情况:
root
和subRoot
是完全一样的两棵树;subRoot
是root
左子树中的子树;subRoot
是root
右子树中的子树;
判断两棵数是否完全一致,可以参见 第 100 题 相同的树。
代码
/**
* @param {TreeNode} root
* @param {TreeNode} subRoot
* @return {boolean}
*/
var isSubtree = function (root, subRoot) {
const isSame = (p, q) => {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSame(p.left, q.left) && isSame(p.right, q.right);
};
if (isSame(root, subRoot)) return true;
if (!root) return false;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
250 | 统计同值子树 🔒 | 树 深度优先搜索 二叉树 | ||
508 | 出现次数最多的子树元素和 | 树 深度优先搜索 哈希表 1+ |