跳至主要內容

572. 另一棵树的子树


572. 另一棵树的子树open in new window

🟢   🔖  深度优先搜索 二叉树 字符串匹配 哈希函数  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给定两个非空二叉树 rootsubRoot ,检验  root 中是否包含和 subRoot 具有相同结构和节点值的子树。root 的一个子树包括 root 的一个节点和这个节点的所有子孙。root 也可以看做它自身的一棵子树。

解题思路

可以使用递归来判断,分为三种情况:

  1. rootsubRoot 是完全一样的两棵树;
  2. subRootroot 左子树中的子树;
  3. subRootroot 右子树中的子树;

判断两棵数是否完全一致,可以参见 第 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统计同值子树 🔒open in new window 深度优先搜索 二叉树
508出现次数最多的子树元素和open in new window 深度优先搜索 哈希表 1+