-
Notifications
You must be signed in to change notification settings - Fork 0
/
572. Subtree of Another Tree
56 lines (42 loc) · 1.51 KB
/
572. Subtree of Another Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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].
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
#Solution
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(subRoot == null){
return true;
}
if(root == null){
return false;
}
if(root.val == subRoot.val){
if(isIdentical(root,subRoot)){
return true;
}
}
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public static Boolean isIdentical(TreeNode root, TreeNode subRoot){
if(root == null && subRoot == null){
return true;
}
if(root == null || subRoot == null){
return false;
}
if(root.val == subRoot.val){
return isIdentical(root.left,subRoot.left) && isIdentical(root.right,subRoot.right);
}
return false;
}
}