572. Subtree of Another Tree

題目網址：https://leetcode.cn/problems/subtree-of-another-tree/

題意：給兩棵 BT root 和 subRoot, 求 subRoot 是否為 root 之 subtree。

Solution：

想法：利用 DFS, 先判斷是否為 Same Tree（可參考 100. Same Tree）
若不是的話, 則遞迴判斷 subRoot 是否為 root 之左子樹 or root 之右子樹

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!subRoot) { // subRoot == null, 則一定為 root 之 subtree
            return true;
        }

        if (!root) { // root == null && subRoot != null
            return false;
        }

        if (isSameTree(root, subRoot)) {
            return true;
        }

        return isSubtree(root->left, subRoot) ||
               isSubtree(root->right, subRoot);
    }

private:
    bool isSameTree(TreeNode* p, TreeNode* q){
        if (!(p && q)) {
            return p == q;
        }

        return (p->val == q->val) &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }
};

令 root 的 node 個數為 m, subRoot 的 node 個數為 n
令 root 的深度為 s, subRoot 的深度為 t

• time：$O(m \cdot n)$ ➔ 對於 root 中的每個 node s, 都以 s 為 root 檢查 n 個 node
• space：$O(max(s, t))$ ➔ 遞迴最大深度