###### tags: `LeetCode` `Tree` `Easy` `Recursion`
# LeetCode #572 [Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)
### (Easy)
給你兩棵二元樹 root 和 subRoot 。檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。如果存在，返回 true ；否則，返回 false 。

二元樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有後代節點。 tree 也可以看做它自身的一棵子樹。

---
與 #100 Same Tree類似, 寫一函式確認是否是相同樹, 接著回傳root與subRoot的相同樹比對或是root->left與subRoot, root->right與subRoot的子樹比對即可。時間複雜的O(n)。

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        return subtree(root, subRoot);
    }
    bool issame(TreeNode* node1, TreeNode* node2){
        if(!node1&&!node2)return true;
        else if((!node1&&node2)||(node1&&!node2))return false;
        else if(node1&&node2)return (node1->val==node2->val)&&issame(node1->left,node2->left)&&issame(node1->right,node2->right);
        return false;
    }
    bool subtree(TreeNode* root, TreeNode* node){
        if(!root)return false;
        else if(root->val==node->val)return issame(root, node)||subtree(root->left, node)||subtree(root->right, node);
        else return subtree(root->left, node)||subtree(root->right, node);
    }
};

---
LeetCode上更快的寫法(線性時間)

root為主要樹, subRoot為比較樹, 確認subRoot是否為root的子樹。

getDepth函式負責確認節點高度, 首先先呼叫getDepth(subRoot,-1)得到subTree的高度, 代表在比較樹高時, 只有在該高度的樹有可能符合條件成為子樹。

接下來呼叫getDepth(root,getDepth(subRoot,-1)), 代表找到root樹中高度為getDepth(subRoot,-1)的節點, 只有高度符合的節點能成為比對子樹的候選者。

將符合的節點放入數組中,並一一進行sametree比對, 這樣省去了遞迴的時間,時間複雜度為O(n)。

class Solution {
    vector<TreeNode*> nodes;

public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root && !subRoot) return true;
        if (!root || !subRoot) return false;

        getDepth(root, getDepth(subRoot, -1));

        for (TreeNode* n: nodes){
            if (identical(n, subRoot))
                return true;
        }
        return false;
    }

    int getDepth(TreeNode* node, int d) {
        if (!node)
            return -1;

        int depth = max(getDepth(node->left, d), getDepth(node->right, d)) + 1;
        
        // Check if depth equals required value
        // Require depth is -1 for tree t (only return the depth, no push)
        if (depth == d)
            nodes.push_back(node);

        return depth;
    }

    bool identical(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (!a || !b || a->val != b->val) return false;

        return identical(a->left, b->left) && identical(a->right, b->right);
    }
};