572. Subtree of Another Tree.md

572. Subtree of Another Tree

思路

让我们求一个数是否是另一个树的子树，从题目中的第二个例子中可以看出，中间某个部分的不能算是子树。如果从s的某个结点开始，跟t的所有结构都一样就可以了，所以问题转换为判断两树是否相等，即100. Same Tree。

C++

class Solution {
private:
    bool isSameTree(TreeNode* t1, TreeNode* t2){
        if(!t1 || !t2) return (!t1 && !t2);
        return (t1 -> val == t2 -> val) && \
               isSameTree(t1 -> left, t2 -> left) && \
               isSameTree(t1 -> right, t2 -> right);
    }
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s) return t == NULL;
        if(!t) return true;
        return isSameTree(s, t) || isSubtree(s -> left, t) || isSubtree(s -> right, t);
    }
};