跳至主要內容

26. 树的子结构


26. 树的子结构open in new window

🟠   🔖  深度优先搜索 二叉树  🔗 力扣open in new window

题目

给定两棵二叉树 tree1tree2,判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。 注意,空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值

示例 1:

输入:tree1 = [1,7,5], tree2 = [6,1]

输出:false

解释:tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2:

输入:tree1 = [3,6,7,1,8], tree2 = [6,1]

输出:true

解释:tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

提示:

  • 0 <= 节点个数 <= 10000

解题思路

这个问题可以通过递归的方式来解决。对于二叉树 tree1 中的每个节点,都检查以该节点为根的子树是否与 tree2 结构相同,即判断它们是否有相同的结构和节点值。如果是,就返回 true,否则继续递归检查左右子树。

代码

function isSubStructure(tree1, tree2) {
	// 判断两个树是否相同的函数
	function isSameTree(node1, node2) {
		if (!node2) {
			return true; // node2 节点都为空,认为相同
		}
		if (!node1 || node1.val !== node2.val) {
			return false; // node1 节点为空,或者两个节点值不相等,认为不相同
		}
		// 递归判断左右子树是否相同
		return (
			isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right)
		);
	}

	// 遍历 tree1 中的每个节点,检查是否有与 tree2 结构相同的子树
	function traverse(node) {
		if (!node || !tree2) {
			return false; // 当前节点为空,或 tree2 为空树,不是子树
		}
		if (isSameTree(node, tree2)) {
			return true; // 找到相同结构的子树
		}
		// 递归检查左右子树
		return traverse(node.left) || traverse(node.right);
	}

	return traverse(tree1);
}