19ms C++ solution beats 99.9%

  • 9

    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;
        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)
            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

    Nice optimization! One more function, but much faster.

  • 0

    This is a clever&simple implement.

  • 0

    @vicch7 Very clever solution! I have a thought, that might improve a little bit of speed. Inside getDepth subroutine before doing nodes.push_back(r) your are checking "if (depth == d)", if you manage to add another condition as in "if (depth == d && r->val == t->val)" the node which doesn't match with the root value of t is not pushed to nodes vector.

Log in to reply

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