剑指Offer_17

发表于 | 分类于

题目

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

解题思路

判断树root2是不是root1的子树

a. 在主函数HasSubtree中，先设置了而标志位ret为false，当从辅助函数isSubtree返回true之后，就退出递归，否则， 继续递归。如果在主函数中输入的root1和root2其一为null时，程序退出。

b. 进入辅助函数isSubtree的条件是， 当前两个树的节点值是一样的。

c. ret返回true的条件是，root2的每个节点值都等于对应的root1的节点值，直到root2为null。

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
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private boolean isSubtree(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        //当root2 != null 而 root1 == null 时，肯定不是子树
        if(root1 == null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }
        //如果上述条件都通过，递归判断是否子树
        return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
    }
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean ret = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                ret = isSubtree(root1, root2);
            }
            if(ret == false){
                ret = HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
            }
        }
        return ret;
    }
    
}