树的子结构

题目描述

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

分析

使用递归，依次对比。

实现

 public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null){
        return false;
        }
        return isSubTree(root1,root2) || HasSubtree(root1.left,root2)
            || HasSubtree(root1.right,root2);
        }

       public boolean isSubTree(TreeNode node1, TreeNode node2) {
        // 说明对比完了
        if (node2 == null) {
            return true;
        }
        if (node1 == null || node1.val != node2.val) {
            return false;
        }
        // 对于的话就匹配子节点
        return isSubTree(node1.left,node2.left) && isSubTree(node1.right,node2.right);
    }