【剑指offer】-树的子结构-17/67

1. 题目描述

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

2. 题目分析

在这里插入图片描述
两颗二叉树A和B,右边的树B是左边树A的子结构

  1. 要查找树A中是否存在和树B结构一样的子树,我们可以分为两步:
    a. 第一步,在树A种找到和树B的根节点的值一样的节点R
    b. 第二步,判断树A中以R为根节点的子树是不是包括和树B一样的结构。
  2. 以上面的两棵树来分析这个过程。首先试着在树A中找到值为8(树B的根节点的值)的节点。从树A的根节点开始遍历,我们发现树A的根节点就是8,。接着判断树A根节点的左子树和右子树是不是和树B的左子树和右子树一样。
  3. 此题中可知,根节点的左子树和右子树并不一样。仍需要遍历树A,接着继续查找值为8的节点。我们在树A的第二层找到了一个数值为8的节点,然后进行第二步的判断,既判断这个节点下面的子树是不是和树B一样的结构。

3. 题目代码

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
public class Solution {
public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean a = false;
if(root1 != null && root2 != null){
if(root1.val == root2.val){
a = Tree(root1,root2);
}
if(!a){
a = HasSubtree(root1.left,root2);
}
if(!a){
a = HasSubtree(root1.right,root2);
}
}
return a;
}
public static boolean Tree(TreeNode root1, TreeNode root2){
if(root2 == null){
return true;
}
if(root1 == null){
return false;
}
if(root1.val != root2.val){
return false;
}
return Tree(root1.left,root2.left) && Tree(root1.right,root2.right);
}
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信