剑指Offer-Java-树的子结构

package com.sjsq.test;

/**
 * @author shuijianshiqing
 * @date 2020/5/19 20:47
 */

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */

public class Solution {

    public boolean HasSubtree(TreeNode root1,TreeNode root2){
        boolean result = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                result = HasTree(root1,root2);
            }
            if(!result){
                result = HasTree(root1.left,root2);
            }
            if(!result){
                result = HasTree(root1.right,root2);
            }
        }
        return result;
    }

    public boolean HasTree(TreeNode root1,TreeNode root2){

        //首先是递归结束条件，递归到B没有子节点时，说明比较完了，B是A子结构
        //遍历到A没有子节点时，说明还有B的子孙节点没有比较，此时B不是A的结构
        //这两句的顺序不能颠倒，因为先判断的B树是否还有节点。
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }

        //到这里说明传入的两颗树的根节点值相同
        return HasTree(root1.left,root2.left) && HasTree(root1.right,root2.right);
    }
}
  
 

  
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
 

文章来源: blog.csdn.net，作者：水坚石青，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/helongqiang/article/details/106223508