[검지offer-Java판] 18 나무의 자 구조.

    public class _Q18 {

    public boolean HasSubTree(BinaryTreeNode tree1, BinaryTreeNode tree2) {
        if (tree1 == null) return false;
        if (tree2 == null) return true; //  ， 

        boolean result = false;
        if (tree1.value == tree2.value) {
            result = DoesTree1HasTree2(tree1, tree2);
        }
        if (!result) { //  
            result = HasSubTree(tree1.leftChild, tree2);
        }
        if (!result) { //  
            result = HasSubTree(tree1.rightChild, tree2);
        }

        return result;
    }

    private boolean DoesTree1HasTree2(BinaryTreeNode tree1, BinaryTreeNode tree2){
        if(tree2 == null) return true;
        if(tree1 == null) return false;

        boolean result = false;
        if(tree1.value != tree2.value){
            return false;
        }else{
            result = DoesTree1HasTree2(tree1.leftChild, tree2.leftChild) 
                    && DoesTree1HasTree2(tree1.rightChild, tree2.rightChild);
        }

        return result;
    }
    }

    public class _Q18Test extends TestCase {

    _Q18 subTree = new _Q18();

    public void test(){
        BinaryTreeNode node0 = new BinaryTreeNode();
        BinaryTreeNode node1 = new BinaryTreeNode();
        BinaryTreeNode node2 = new BinaryTreeNode();
        BinaryTreeNode node3 = new BinaryTreeNode();
        BinaryTreeNode node4 = new BinaryTreeNode();
        BinaryTreeNode node5 = new BinaryTreeNode();
        BinaryTreeNode node6 = new BinaryTreeNode();

        BinaryTreeNode node7 = new BinaryTreeNode();
        BinaryTreeNode node8 = new BinaryTreeNode();
        BinaryTreeNode node9 = new BinaryTreeNode();

        node0.value = 8;
        node1.value = 8;
        node2.value = 7;
        node3.value = 9;
        node4.value = 2;
        node5.value = 4;
        node6.value = 7;

        node7.value = 8;
        node8.value = 9;
        node9.value = 2; //  tree1 

        node0.leftChild = node1;
        node0.rightChild = node2;
        node1.leftChild = node3;
        node1.rightChild = node4;
        node4.leftChild = node5;
        node4.rightChild = node6;

        node2.leftChild = null; node2.rightChild = null;
        node3.leftChild = null; node3.rightChild = null;
        node5.leftChild = null; node5.rightChild = null;
        node6.leftChild = null; node6.rightChild = null;

        node7.leftChild = node8;
        node7.rightChild = node9;

        node8.leftChild = null; node8.rightChild = null;
        node9.leftChild = null; node9.rightChild = null;

        System.out.println(subTree.HasSubTree(null, node7));
    }
    }