Slower C++ recursive solution with detailed explanation (still worth to share)


  • 0

    Only after I saw many posts by other coders, I realized that my recursive solution is not good. However, I still think it is worth to share think this is how my thinking process works for recursion.

    The idea is simple. For tree related problems, I always consider how we can derive the answer for a tree based on results of its left and right subtrees. Supposed we have a tree root and already calculated the path sum of root->left and root->right, then we just need to prefix root->val to each path from left/right subtrees. However, different paths have different length, so we don't know the position of digit root->val. It turns out that, we need also keep the depths of all leaves during recursion, so we know how to increment the path sum of subtrees to get the path sum of final results.

    • 1: If the root has no leaf, just return its digit value;
    • 2: Get the path sum of subtree(s) and array of leaf depths;
    • 3: The total path sum will be the sum of subtree(s) + root->val treated as the prefix of every path (i.e., multiplied by pow(10, d+1), where d is the leaf depth in subtree)

    The reason to keep the leaf depth because it works backwards to form a multi-digit integer. If I had worked to form integer forwards (like many other coders did), then simply prefix*10 + last_digit would give the number after incorporating one more digit. Anyway, here is my code if you are interested.

        int sumNumbers(TreeNode* r) {
            vector<int> leafDepth;
            return helper(r, leafDepth);
        }
        
        int helper(TreeNode* r, vector<int>& leafDepth) {
            if (!r) return 0;
            if (!r->left && !r->right) {
                leafDepth = {0}; return r->val;
            }
            vector<int> rLeafDepth;
            int Lsum = helper(r->left, leafDepth);
            int Rsum = helper(r->right, rLeafDepth);
            int sum = Lsum + Rsum;
            for (int x:leafDepth) sum += pow(10, x+1)*r->val;
            for (int x:rLeafDepth) sum += pow(10, x+1)*r->val;
            leafDepth.insert(leafDepth.end(), rLeafDepth.begin(), rLeafDepth.end());
            for (int& x:leafDepth) x++;
            return sum;
        }
    

Log in to reply
 

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