题目的意思：

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

例子1

下图是第一个例子，可以看到 B 是 A 的子结构。

image

第一个例子的判断逻辑是：

• 比较当前节点值

• 递归比较左右节点的值

• 直到遍历完 B 树

例子 2

下图是第二个例子，可以看到 B 也是 A 的子结构。

image

但是 A 的根节点和 B 的根节点并不相同。因此对于这种情况，需要对 A 树进行递归遍历。如果 B 是 A 的左子树或者右子树的子结构，那么也是可以的。

思想：

1. 首先需要判断A,B的根节点是否一样。

2. 如果不一样，判断A的左孩子和B的根节点是否一样，同理可判断A的右孩子和B的根节点是否一样。依次找下去

如果上述情况都不满足则说明不包含

1.如果找到了A中有值和B中的根节点相同，则比较左右子树是否相同。

2.如果B为空了，则说明包含

3.如果A为空了，则说明不包含

C++

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

TreeNode(int x) :

val(x), left(NULL), right(NULL) {

}

};*/

class Solution {

public:

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2);

    bool judge(TreeNode* root, TreeNode* subTree);

};

bool Solution :: HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)

{

        if(pRoot1 == NULL || pRoot2 ==NULL)

            return false;

        if(pRoot1->val == pRoot2->val){

            if(judge(pRoot1, pRoot2))

            {

                return true;

            }

        }

        return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);

}

bool Solution :: judge(TreeNode* root, TreeNode* subTree)

{

        if(subTree == NULL)

        {

            return true;

        }

        if(root == NULL)

        {

            return false;

        }

        if(root->val == subTree->val)

        {

            return judge(root->left, subTree->left) && judge(root->right,subTree->right);

        }

        return false;

}

java

public class Solution {

    //遍历大树
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null){
            return false;
        }
        //如果找到与子树相同根的值，走判断方法
        if(root1.val == root2.val){
            if(judge(root1,root2)){
                return true;
            }
        }
        //遍历左孩子，右孩子
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    //判断是否是子结构
    public boolean judge(TreeNode root, TreeNode subtree) {
        //子结构已经循环完毕，代表全部匹配
        if(subtree == null){
            return true;
        }
        //大树已经循环完毕，并未成功匹配
        if(root == null){
            return false;
        }
        //相等后判断左右孩子
        if(root.val == subtree.val){
            return judge(root.left, subtree.left) && judge(root.right, subtree.right);
        }
        return false;
    }
}