Approach #1 Using Preorder Traversal [Accepted]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/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private String preorder(TreeNode node){
if(node==null) return "null";
return "#"+node.val+preorder(node.left)+preorder(node.right);
}
public boolean isSubtree(TreeNode s, TreeNode t) {
String str_s=preorder(s);
String str_t=preorder(t);
return str_s.contains(str_t);
}
}
Approach #2 By Comparison of Nodes [Accepted]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/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private boolean equals(TreeNode x,TreeNode y){
if(x==null&&y==null) return true;
if(x==null||y==null) return false;
return x.val==y.val&&equals(x.left,y.left)&&equals(x.right,y.right);
}
private boolean traverse(TreeNode s,TreeNode t){
return s!=null&&(equals(s,t)||traverse(s.left,t)||traverse(s.right,t));
}
public boolean isSubtree(TreeNode s, TreeNode t) {
return traverse(s,t);
}
}
