剑指Offer-树的子结构

发表于 | 阅读次数 | 阅读数

树的子结构

题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路先找同一个根节点，然后进行匹配ß  两次递归

思路

首先找到相同的根节点，然后递归是否相同

代码

public class HasSubTree {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

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

        }

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

    }

    private boolean DoesTree1HaveTree2(TreeNode roo1, TreeNode root2) {
        if (roo1 == null && root2 != null) return false;
        if (root2 == null) return true;
        if (roo1.val != root2.val) {
            return false;
        }

        return DoesTree1HaveTree2(roo1.left, root2.left) && DoesTree1HaveTree2(root2.right, root2.right);
    }
    /**
     * 输入两棵二叉树A和B，判断B是不是A的子结构。
     * 该方法是在A树中找到一个与B树的根节点相等的元素的结点，
     * 从这个相等的结点开始判断树B是不是树A的子结构，如果找到其的一个就返回，
     * 否则直到所有的结点都找完为止。
     *
     * @param root1 树A的根结点
     * @param root2 树B的根结点
     * @return true：树B是树A的子结构，false：树B是不树A的子结构
     */
    public boolean HasSubtree_II(TreeNode root1,TreeNode root2){
        if (root1==root2){
            return true;
        }

        if (root2==null){
            return true;
        }

        if (root1==null){
            return false;
        }

        boolean result = false;

        if (root1.val==root2.val){
            result = match(root1,root2);
        }

        if (result){
            return true;
        }

        return HasSubtree_II(root1.left,root2)||HasSubtree_II(root1.right,root2);
    }
    /**
     * 从树A根结点root1和树B根结点root2开始，一个一个元素进行判断，判断B是不是A的子结构
     *
     * @param root1 树A开始匹配的根结点
     * @param root2 树B开始匹配的根结点
     * @return 树B是树A的子结构，false：树B是不树A的子结构
     */
    private boolean match(TreeNode root1, TreeNode root2) {

        if (root1==root2){
            return true;
        }

        if (root2==null){
            return true;
        }

        if (root1==null){
            return false;
        }

        if (root1.val==root2.val){
            return match(root1.left,root2.left)&&match(root1.right,root2.right);
        }

        return false;
    }
}
0%