Straight forward solution


  • 1
    K
    class Solution {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) {
            if(s == nullptr && t == nullptr) return true;
            if(t == nullptr) return true;
            if(s == nullptr) return false;
            
            return sameTree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
        }
        
        bool sameTree(TreeNode* s, TreeNode* t){
            if(s == nullptr && t == nullptr) return true;
            if(s == nullptr || t == nullptr) return false;
            if(s->val != t->val) return false;
            
            return sameTree(s->left, t->left) && sameTree(s->right, t->right);
        }
        
    };

  • 0
    D

    The same idea

    class Solution {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) {
            return helper(s,t) || ((s)?isSubtree(s->left,t) || isSubtree(s->right,t):false);
        }
        
        bool helper(TreeNode* s, TreeNode* t) {
            if (s && t && s->val == t->val) {
                return helper(s->left, t->left) && helper(s->right, t->right);
            } else if (s == NULL && t == NULL) {
                return true;
            }
            return false;
        }
        
    };
    

  • 0
    T

    Can anyone tell me the time Complexity of this Code ?
    I am thinking it as O(n2) because both the functions are traversing the tree.
    And also how to compute time complexity of this kind of recursive functions ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.