树的子结构

题目：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

牛客网leetcode

解法思路

1. 如果B树为空，返回false
2. 如下例子中，节点值为4的节点a在A中存在，此时需要判断B根节点的左子树和右子树是否为A树中a节点的左子树和右子树的子结构？如果B树中某个子树为NULL则不需要考虑A树中对应的节点是否为NULL，直接返回true。当B树的左右子树为a节点左右子树的子结构返回true。通过递归调用即可。
3. 设置一个全局变量来标志B树是否为A树的子结构，如果已经在A树中找到B树的子结构，则A树不用继续遍历。

给定的树 A:
     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool s = false;
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot2 || !pRoot1) return false;
        search(pRoot1, pRoot2);
        return s;
    }

    void search(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (s) return;
        if (!pRoot1) return;
        if (pRoot1->val == pRoot2->val) s = subTree(pRoot1, pRoot2);
        search(pRoot1->left, pRoot2);
        search(pRoot1->right, pRoot2);
    }
    
    bool subTree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot2) return true;
        return pRoot1 && pRoot1->val == pRoot2->val && subTree(pRoot1->left, pRoot2->left) && subTree(pRoot1->right, pRoot2->right);
    }
};