小景哥哥

世界很大,而我们还需要再成长!

您现在的位置是:首页>爱编程>详细内容

树的子结构

发布时间:2018-08-13 00:00:00编辑:Jason浏览(148)评论(0)

    17.树的子结构

    题目描述

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

    比较两棵树当前根节点是否相等,相等的话再递归分别比较左右子树是否包含相同结构。

     


    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) {
            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;
        }
        
        public boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2){
            if(root2 == null)
                return true;
            if(root1 == null)
                return false;
            
            if(root1.val != root2.val)
                return false;
            return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
        }
    }

关键字词:offer