572. 另一棵树的子树

题目描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

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

示例 1：

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

示例 2：

输入：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

---

解题分析及思路：

方法：深度优先搜索

思路：

利用深度优先搜索遍历树，判断根节点是否与子树的根节点相同

• 如果相同，则判断子树是否与子树的根节点相同
  • 如果相同，则返回true
  • 否则返回false
• 如果根节点与子树的根节点不同，则继续遍历左子树和右子树。

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	if root == nil {
		return false
	}
	if root.Val == subRoot.Val && isSameTree(root, subRoot) {
		return true
	}
	return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func isSameTree(root *TreeNode, subRoot *TreeNode) bool {
	if root == nil && subRoot == nil {
		return true
	}
	if root == nil || subRoot == nil {
		return false
	}
	if root.Val != subRoot.Val {
		return false
	}
	return isSameTree(root.Left, subRoot.Left) && isSameTree(root.Right, subRoot.Right)
}

复杂度：

• 时间复杂度：O(N * M)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:12 ms,击败了58.32% 的Go用户
• 内存消耗:6.4 MB,击败了66.07% 的Go用户