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);
        }
    }
};