面试题26：树的子结构

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

class BinaryTreeNode{
        double value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

思路：通过递归来实现。先判断A和B的根节点是不是相等，如果相等则比较剩下的节点，如果不相等则用A根节点的左节点和B比较，如果还不相等则用A的右节点和B比较，以此类推。
解决方案：

public class Question26 {
    static class BinaryTreeNode{
        double value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }
    public static boolean equal(double num1, double num2){
        if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)){
            return true;
        }else {
            return false;
        }
    }
    public static boolean doesTreeHaveTree2(BinaryTreeNode root1, BinaryTreeNode root2){
        if (root2 == null){
            return true;
        }
        if (root1 == null){
            return false;
        }
        if (!equal(root1.value, root2.value)){
            return false;
        }
        return doesTreeHaveTree2(root1.left, root2.left) && doesTreeHaveTree2(root1.right, root2.right);
    }
    public static boolean hasSubTree(BinaryTreeNode root1, BinaryTreeNode root2){
        boolean result = false;
        if (root1 != null && root2 != null){
            if (equal(root1.value, root2.value)){
                result = doesTreeHaveTree2(root1, root2);
            }
            if (!result){
                result = hasSubTree(root1.left, root2);
            }
            if (!result){
                result = hasSubTree(root1.right, root2);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        BinaryTreeNode pHead = new BinaryTreeNode(1);
        BinaryTreeNode pAhead = new BinaryTreeNode(3);
        BinaryTreeNode pBhead = new BinaryTreeNode(5);
        BinaryTreeNode pChead = new BinaryTreeNode(7);
        pHead.left = pAhead;
        pHead.right = pBhead;
        pBhead.left = pChead;

        BinaryTreeNode pHead2 = new BinaryTreeNode(1);
        BinaryTreeNode pAhead2 = new BinaryTreeNode(3);
        BinaryTreeNode pBhead2 = new BinaryTreeNode(5);
        pHead2.left = pAhead2;
        pHead2.right = pBhead2;
        System.out.println(hasSubTree(pHead, pHead2));
    }
}