這道題目要求我們判斷一棵樹 root 是否包含另一棵樹 subRoot 作為它的子樹。也就是說，從 root 的某個節點開始，該節點及其子樹的結構與 subRoot 完全一致。

題目：

給定兩棵二元樹 root 和 subRoot，我們需要判斷 subRoot 是否是 root 的子樹。如果在 root 中存在一個節點，其對應的子樹和 subRoot 一模一樣，那麼我們就說 subRoot 是 root 的子樹。

• 輸入：二元樹的根節點 root 和 subRoot。
• 輸出：布林值，若 subRoot 是 root 的子樹，回傳 true；否則，回傳 false。

範例：

範例 1：

輸入：
root: 
     3
   /   \
  4     5
 / \
1   2

subRoot: 
   4
  / \
 1   2

輸出：true

範例 2：

輸入：
root: 
     3
   /   \
  4     5
 / \
1   2
   /
  0

subRoot: 
   4
  / \
 1   2

輸出：false

解題思路

拿著subRoot樹比去對root樹比對，所以會想到怎麼做比較有效率，先用subtRoot的root節點的值去搜尋目標樹，在目標樹上有找到跟subRoot root節點相同值的話，再進行後續的子樹比對，整個思路會是這樣的方向，

打算用BFS的方式在目標樹上搜尋subRoot root節點的值，

比對兩個二元樹是否相同的話，這個在 leetcode 100 已經練習過了，思路就直接拿來套即可，

實作：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSametree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr)
            return true;
        if (p == nullptr || q == nullptr)
            return false;

        if (p->val != q->val)
            return false;

        return isSametree(p->left, q->left) && isSametree(p->right, q->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr && subRoot == nullptr)
            return true;
        if (root->val == subRoot->val) {
            bool res = isSametree(root, subRoot);
            if (res) return true;
        }

        if (root->left) {
            bool res = isSubtree(root->left, subRoot);
            if (res) return true;
        }

        if (root->right) {
            bool res = isSubtree(root->right, subRoot);
            if (res) return true;
        }

        return false;
    }
};

參考：
#572. Subtree of Another Tree