《剑指offer第二版》面试题26：树的子结构（java）

题目描述

输入二叉树A和B，判断B是不是A的子结构。

解题思路:

1. 采用递归的方式判断。
2. 先判断以A为根节点的子树是否和B具有相同结构。
3. 如果不同，则继续判断A的左右子树是否存在和B相同结构的子树。

代码

// 判断rootB是否是rootA的子结构
boolean hasSubTree(TreeNode rootA, TreeNode rootB) {
    if (rootA == null && rootB == null) {
        return true;
    }
    if (rootA == null) {
        return false;
    }

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

    if (isSubTree(rootA, rootB)) {
        // 说明rootB和rootA根节点的子树具有相同结构
        return true;
    }
    // 继续判断rootA的左右子树是否存在和rootB相同结构的子树
    return  hasSubTree(rootA.left, rootB) || hasSubTree(rootA.right, rootB);
}
// 从根节点开始比较，判断rootB是否是rootA的子结构
boolean isSubTree(TreeNode rootA, TreeNode rootB) {
    if (rootA == null && rootB == null) {
        return true;
    }

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

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

    if (rootA.value != rootB.value) {
        return false;
    }
    return isSubTree(rootA.left, rootB.left) && isSubTree(rootA.right, rootB.right);
}