Fork me on GitHub

树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

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
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
//当Tree1和Tree2都不为零的时候,才进行比较。否则直接返回false
if( root1!=null && root2!=null){
//如果找到了对应Tree2的根节点的点
if(root1.val==root2.val){
//以这个根节点为为起点判断是否包含Tree2
result=doesTree1HasTree2(root1,root2);
}
//如果找不到,那么就再去root的左儿子当作起点,去判断时候包含Tree2
if(!result){
result=HasSubtree(root1.left,root2);
}
//如果还找不到,那么就再去root的右儿子当作起点,去判断时候包含Tree2
if(!result){
result=HasSubtree(root1.right,root2);
}
}
//返回结果
return result;
}

public static boolean doesTree1HasTree2(TreeNode node1,TreeNode node2){
//如果Tree2已经遍历完了都能对应的上,返回true
if(node2==null){
return true;
}
//如果Tree2还没有遍历完,Tree1却遍历完了。返回false
if(node1==null){
return false;
}
//如果其中有一个点没有对应上,返回false
if(node1.val!=node2.val){
return false;
}
//如果根节点对应的上,那么就分别去子节点里面匹配
return doesTree1HasTree2(node1.left,node2.left) && doesTree1HasTree2(node1.right,node2.right);
}
}

钱聪 wechat
欢迎交流学习。
么么!