【剑指Offer题解：java】树的子结构

题目

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

分析

1. 先序遍历树 A中的每个节点node1
2. 判断树A中以node1为根节点的子树是否包含树B

终止条件：

• 当节点 node2为空：说明树B已匹配完成（越过叶子节点），因此返回 true
• 当节点 node1 为空：说明已经越过树 A叶子节点，即匹配失败，返回 false
• 当节点 node1和 node2 的值不同：说明匹配失败，返回 false

判断 A 和 B 的左子节点是否相等

判断 A 和 B 的右子节点是否相等

代码

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

    public boolean HasSubtree2(TreeNode node1, TreeNode node2) {
        if (node2 == null) return true;
        if (node1 == null || node1.val != node2.val) return false;//node2还不为空
        return HasSubtree2(node1.left, node2.left) && HasSubtree2(node1.right, node2.right);
    }