题目描述

输入两棵二叉树 $A$，$B$，判断 $B$ 是不是 $A$ 的子结构。
我们规定空树不是任何树的子结构。

数据范围

每棵树的节点数量 $[0,1000]$。

样例

树 A：

     8
    / \
   8   7
  / \
 9   2
    / \
   4   7
树 B：

   8
  / \
 9   2
返回 true，因为 B 是 A 的子结构。

思路

这道题的思路是找到一个结点能满足等于根节点，然后再对比左右子树，看是否相同。
对于样例来说，先找$A$的根节点$8$，发现$8$的左儿子$8$不等于$B$中的$9$，所以就在尝试根节点$8$的左儿子$8$，发现恰好满足了。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //题目规定，空树返回false
        if (pRoot1 == NULL || pRoot2 == NULL)
            return false;
        //如果当前结点pRoot1可以匹配的话，就返回true
        if (same(pRoot1, pRoot2))
            return true;
        //尝试左右儿子
        return hasSubtree(pRoot1 -> left, pRoot2) || hasSubtree(pRoot1 -> right, pRoot2);
    }

    bool same(TreeNode* p1, TreeNode* p2)
    {
        //如果B已经被匹配完了说明为真
        if (p2 == NULL) 
            return true;
        //如果A已经被匹配完了但B还没完或p1根本不等于p2
        if (!p1 || p1 -> val != p2 -> val) 
            return false;
        //递归处理左右子树
        return same(p1 -> left, p2 -> left) && same(p1 -> right, p2 -> right);
    }
};

好了，这篇题解到这里就结束了。感谢观看！

Thanks♪(･ω･)ﾉ！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$