题目
输入两棵二叉树A，B，判断B是不是A的子结构。
我们规定空树不是任何树的子结构。
样例
树A：
8
/ \
8 7
/ \
9 2
/ \
4 7
树B：
8
/ \
9 2
返回 true ,因为B是A的子结构。

解法：递归

这道题实际上是把字符串匹配迁移到了二叉树上
采用递归的做法（还是得好好锻炼递归思维）

  • 首先看根结点能否匹配上
  • 不能就接着看左子树和右子树

匹配的时候

  • 如果t2为空，说明这部分已经匹配上
  • 如果t2不为空但是t1为空，没匹配上
  • 如果都不为空，就看t1和t2的值是否相等

时间复杂度O(nm)，空间复杂度O(1)

  • n代表t1中结点数目，m代表t2中结点数目

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8. * };
    9. */
    10. class Solution {
    11. public:
    12.   bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    13.       if (!pRoot1 || !pRoot2) return false;
    14.       if (isSame(pRoot1, pRoot2)) return true;
    15.       return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    16.   }
    18.   bool isSame(TreeNode* t1, TreeNode* t2) {
    19.       if (!t2) return true;
    20.       if (!t1 || t1->val != t2->val) return false;
    21.       return isSame(t1->left, t2->left) && isSame(t1->right, t2->right);
    22.   }
    23. };