572. Subtree of Another Tree
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.
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
Example
https://assets.leetcode.com/uploads/2021/04/28/subtree1-tree.jpg
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
思路
先去做100. Same Tree[Easy]
,再次基础上,加上遍历每一个节点,就能得出是否含有子树
题解
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// 如果目标子树为null 直接返回true
if (subRoot == null)
return true;
// 如果当前遍历节点已为null 在目标子树不为null 的基础上,返回false
if (root == null)
return false;
// 判断当前子树是否相等
if (isSameTree(root, subRoot))
return true;
//没有命中结束条件就继续遍历
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSameTree(TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null)
return true;
if ((n1 == null || n2 == null) || (n1.val != n2.val))
return false;
return isSameTree(n1.left, n2.left) && isSameTree(n1.right, n2.right);
}
标签:return,true,572,tree,Tree,subRoot,Easy,null,root
From: https://www.cnblogs.com/tanhaoo/p/17096296.html