19ms C++ solution beats 99.9%


  • 7
    V

    Two trees are identical when they are recursively identical. Brute force solution would be recursively compare each node in s with t to check for identical. Better solution is to only compare nodes in s with the same max depth as t. First get max depth of t, then recursively check each node in s, if depth equals, push to a vector. Then compare each node in the vector with t.

    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;
    
            // 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(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);
        }
    };
    

  • 0
    F

    Nice optimization! One more function, but much faster.


  • 0
    C

    This is a clever&simple implement.


Log in to reply
 

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