# 572. Subtree of Another Tree

## 1.問題 

## 2.想法

* 提問
  * 確認題意:  subtree的定義是有著完全一樣的childrens
* function header, parameter
* test input
* 說明想法
  * Root相同, 直接比較child是否相同
  * Root不同, 則t可能包含於s的左子或右子樹, 當root相同時便開始進行比較
  * DFS, 一邊向下搜尋一邊檢查以下情形, 如果符合則回傳NULL:
    * s, t的值不同
    * s, t有一邊為NULL
* 測試計算複雜度

## 3.程式碼

```

/**
 * 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 isSubtree(TreeNode* s, TreeNode* t) {
        if (!s) {
            return false;
        } else if (s->val == t->val && matchSubtree(s, t)) {
            return true; 
        }
        
        return isSubtree(s->left, t) || isSubtree(s->right, t); 
    }
private:
    bool matchSubtree(TreeNode* s, TreeNode* t) {
        if (!s && !t) {
            return true;
        } else if (!s || !t) {
            return false;
        } else if (s->val != t->val) {
            return false;
        } else {
            return matchSubtree(s->left, t->left) && matchSubtree(s->right, t->right);
        }
    }
};
```