树的子结构

题目：输入两棵二叉树A和B，判断B是不是A的子结构。例如下图中的两棵二叉树，由于A中有一部分子树的结构和B是一样的，因此B是A的子结构。

这里写图片描述

如果 后者是前者的一个子结构
步骤

1. 在树A中找到和B的根结点的值一样的结点R；
2. 判断树A中以R为根结点的子树是不是包含和树B一样的结构。很明显，这是一个递归的过程。

  boolean HasSubtree(BinaryTreeNode pRoot1,BinaryTreeNode pRoot2){
        boolean result=false;

        if (pRoot1!=null&&pRoot2!=null){
            if (pRoot1.getValue()==pRoot2.getValue()){
                result=DoesTree1HaveTree2(pRoot1,pRoot2);
            }
            if (!result){
                result=HasSubtree(pRoot1.getLeft(),pRoot2);
            }
            if (!result){
                result=HasSubtree(pRoot1.getRight(),pRoot2);
            }
        }
        return result;
    }
    boolean DoesTree1HaveTree2(BinaryTreeNode pRoot1,BinaryTreeNode pRoot2){
        if (pRoot2==null)return true;
        if (pRoot1==null)return false;
        if (pRoot1.getValue()!=pRoot2.getValue())return false;
        return DoesTree1HaveTree2(pRoot1.getLeft(),pRoot2.getLeft())&&DoesTree1HaveTree2(pRoot1.getRight(),pRoot2.getRight());
    }

参考文章：http://www.cnblogs.com/edisonchou/p/4771939.html