572. Subtree of Another Tree

🟢   🔖  树 深度优先搜索 二叉树 字符串匹配 哈希函数  🔗 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 也可以看做它自身的一棵子树。

解题思路

可以使用递归来判断，分为三种情况：

1. root 和 subRoot 是完全一样的两棵树；
2. subRoot 是 root 左子树中的子树；
3. 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);
};

相关题目

相关题目

• 🔒 Count Univalue Subtrees
• 508. 出现次数最多的子树元素和

- [🔒 Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees)
- [508. 出现次数最多的子树元素和](https://leetcode.com/problems/most-frequent-subtree-sum)