Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.ArrayList;
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
if(root1!=null && root2!=null){
result = doesTree1HaveTree2(root1, root2);
if(!result){
result = HasSubtree(root1.left, root2);
}
if(!result){
result = HasSubtree(root1.right, root2);
}
}
return result;
}
private boolean doesTree1HaveTree2(TreeNode root1,TreeNode root2){
if(root2==null){
return true;
}
if(root1==null){
return false;
}
if(root1.val!=root2.val){
return false;
}
return doesTree1HaveTree2(root1.left, root2.left)&&doesTree1HaveTree2(root1.right,root2.right);
}
public TreeNode generateTreeByArray(char[] array){
ArrayList<TreeNode> treeNodes = new ArrayList<>();
if(array==null || array.length<=0 || array[0]=='#'){
return null;
}
TreeNode treeNode = new TreeNode(array[0]-'0');
treeNodes.add(treeNode);
int indexParent = 0;
int indexChild = 1;
while(indexChild<array.length){
if(treeNodes.get(indexParent)!=null){
if(array[indexChild]!='#'){
treeNodes.get(indexParent).left = new TreeNode(array[indexChild]-'0');
treeNodes.add(treeNodes.get(indexParent).left);
}
if(indexChild+1<array.length && array[indexChild+1]!='#'){
treeNodes.get(indexParent).right = new TreeNode(array[indexChild+1]-'0');
treeNodes.add(treeNodes.get(indexParent).right);
}
indexParent++;
indexChild+=2;
}
}
return treeNode;
}
public static void main(String[] args) {
Solution solution = new Solution();
char[] array = {'8','8','7','9','2','#','#','#','#','4','7'};
TreeNode treeNode = solution.generateTreeByArray(array);
char[] array1 = {'8','9','2'};
TreeNode treeNode1 = solution.generateTreeByArray(array1);
boolean flag = solution.HasSubtree(treeNode, treeNode1);
System.out.println();
}
}
class TreeNode{
int val = 0;
TreeNode left = null;
TreeNode right = null;
TreeNode(int k){
val = k;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.