每日一练（剑指offer）树的子结构

描述

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

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

示例

输入：

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

返回值：

true

示例

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

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

    }

}
*/
public class Solution {
    //判断树结构是否相同
    public boolean isSame(TreeNode root1, TreeNode root2) {
        //如果root2为空，则为true（不需要考虑root1的状况）
        if (root2 == null) return true;
        if (root1 == null) return false;
        //判断首节点的值，然后root1与root2的左子树，然后root1与root2的右子树
        return root1.val == root2.val  &&  isSame(root1.left, root2.left)  &&
               isSame(root1.right, root2.right);
    }

    //方法一：递归的方式（利用深度优先遍历的思想）
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //判断root1和root2是否为null（空树不是任意一个树的子结构）
        if (root1 == null || root2 == null) return false;
        //如果首结点不相等，则依次比较左子树、右子树与root2的关系
        return isSame(root1, root2) || HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }
}