剑指offer 17树的子结构

题目描述

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

1、分析

1. 判断A,B的根节点是否一样。

2. 若不一样，判断A的左孩子和B的根节点是否一样，
   同理可判断A的右孩子和B的根节点是否一样。
   如果上述情况都不满足则说明不包含

3. 如果找到了A中有值和B中的根节点相同，则比较左右子树是否相同。

   如果B为空了，则说明包含

   如果A为空了，则说明不包含

2、代码实现

/**

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) {

        if(root1 == null || root2 == null){

            return false;

        }

        //如果找到与子树相同根的值，走判断方法

        if(root1.val == root2.val){

            if(judgement(root1,root2)){

                return true;

            }

        }

        //遍历左孩子，右孩子

        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);

    }

    //判断是否是子结构

    public boolean judgement(TreeNode root1, TreeNode root2) {

        //子结构已经循环完毕，代表全部匹配

        if(root2 == null){//如果B为空了，则说明包含

            return true;

        }

        //大树已经循环完毕，并未成功匹配

        if(root1 == null){//如果A为空了，则说明不包含

            return false;

        }

        //相等后判断左右孩子

        if(root1.val == root2.val){

            return judgement(root1.left, root2.left) && judge(root1.right, root2.right);

        }

        return false;

    }

}