树的子结构 -- java

输入两棵二叉树A和B，判断B是不是A的子结构，二叉树的节点定义如下：

public class BinaryTreeNode {
    double value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

要查找树A中是否存在和树B结构一样的子树，我们可以分成两步：第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。

第一步在树A中查找与根结点的值一样的结点，这实际上就是树的遍历。我们递归调用HasSubtree遍历二叉树A。如果发现某结点的值和树B的头结点的值相同，则调用DoesTree1HaveTree2，做第二步判断。

第二步是判断树A中以R为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点R的值和树B的根结点不相同，则以R为根结点的子树和树B肯定不具有相同的结点；如果它们的值相同，则递归地判断它们各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。

public class HasSubtree {

    
    public static boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {
        boolean result = false;
        if (root1 != null && root2 != null) {
            if(equal(root1.value, root2.value)) {
                result = doesTree1HaveTree2(root1, root2);
            }
            if (!result) {
                result = hasSubtree(root1.left, root2);
            }
            if (!result) {
                result = hasSubtree(root1.right, root2);
            }
        }

        return result;
    }

    
    public static boolean doesTree1HaveTree2(BinaryTreeNode root1, BinaryTreeNode root2) {
        // 递归的终止条件是到达了树1或者树2的叶节点
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }

        if (!equal(root1.value, root2.value)) {
            return false;
        }

        // 如果当前节点相同，那么判断左右子树节点
        return doesTree1HaveTree2(root1.left, root2.left)
                && doesTree1HaveTree2(root1.right, root2.right);

    }

    
    public static boolean equal(double num1, double num2) {
        if ((num1 - num2) > -0.0000001 && (num1 - num2) < 0.0000001) {
            return true;
        } else {
            return false;
        }
    }

    // 测试
    public static void main(String[] args) {
        // 定义树1
        BinaryTreeNode node1 = new BinaryTreeNode(8);
        BinaryTreeNode node2 = new BinaryTreeNode(8);
        BinaryTreeNode node3 = new BinaryTreeNode(7);
        BinaryTreeNode node4 = new BinaryTreeNode(9);
        BinaryTreeNode node5 = new BinaryTreeNode(2);
        BinaryTreeNode node6 = new BinaryTreeNode(4);
        BinaryTreeNode node7 = new BinaryTreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right =  node5;
        node5.left = node6;
        node5.right = node7;

        // 定义树2
        BinaryTreeNode node8 = new BinaryTreeNode(8);
        BinaryTreeNode node9 = new BinaryTreeNode(9);
        BinaryTreeNode node10 = new BinaryTreeNode(2);
        node8.left = node9;
        node8.right = node10;

        System.out.println(hasSubtree(node1, node8)); // true

        // 定义树3
        node8 = new BinaryTreeNode(8);
        node9 = new BinaryTreeNode(9);
        node10 = new BinaryTreeNode(1);
        node8.left = node9;
        node8.right = node10;


        System.out.println(hasSubtree(node1, node8)); // false

    }

}

来自：

《剑指Offer》
Coding-Interviews/树的子结构.md at master · todorex/Coding-Interviews