qiaoxu123
1/8/2019 - 1:23 AM

572. Subtree of Another Tree

遍历二叉树题目，有点难，需要对二叉树的递归遍历有很深的理解，还是有很多地方不到位啊。

  • Approach 1 ： recursive

使用遍历进行比较

  • Approach 2 ： depth compare + recursive

首先判断两棵二叉树的深度，然后再递归判断，减少运算量

recursive.cpp
content_copyfile_download
//Runtime: 28 ms, faster than 30.42%

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s) return false;
        if(isSame(s,t)) return true;
        
        return isSubtree(s->left,t) || isSubtree(s->right,t);
    }
    
    bool isSame(TreeNode* s,TreeNode* t){
        if(!s && !t) return true;
        if(!s || !t) return false;
        if(s->val != t->val) return false;
        
        return isSame(s->left,t->left) && isSame(s->right,t->right);
    }
};
depth.cpp
content_copyfile_download
//Runtime: 28 ms, faster than 30.42%

class Solution {
    vector<TreeNode*> nodes;
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t) return false;
        
        getDepth(s,getDepth(t,-1));
        
        for(TreeNode* n : nodes)
            if(identical(n,t))
                return true;
        
        return false;
    }
    
    int getDepth(TreeNode* r,int d){
        if(!r)
            return -1;
        
        int depth = max(getDepth(r->left,d),getDepth(r->right,d)) + 1;
        
        if(depth == d)
            nodes.push_back(r);
        
        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);
    }
};