3ms and 6ms recursion C++ solution + explanation


  • 1
    L

    All solutions are O(n) run-time.
    6ms solution
    Recursion or BFS or DFS should pop up as you read this problem, I went with recursion. When you are thinking about recursion, its best to look at your base case and ask yourself what are the things you need to get the correct result.
    Some of the questions you want to ask yourself is, what if you were at the left leaf node, what if you were the parent of a left leaf node, what if you were the right leaf node, what if you were a parent of two children?

    So lets start with the first one, what if I was a left leaf node? Next question I ask, how the hell do I know I am the left leaf node? Good question sherlock!
    So that is when I start with creating a new function that accepts two parameters, the node and a bool or int, that is up to you.
    The second parameter will let me know if I am the left node or right node.
    Next question is how do I know I am a leaf?
    So the next check is whether my pointers are both null. Easy enough. If they are, return my node's val, else I will continue my recursion.
    Now that we asked most of the questions I will just allow right nodes to continue recursion since I know if I am a left or right node now.
    Obviously, start all your functions by checking nulls and you should be good to go.
    Hope that helps!

    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if (root == NULL) return 0;
            
            int left = recur(root->left,1);
            int right = recur(root->right, 0);
            
            return left+right;
        }
        
        int recur(TreeNode* root, int i) {
            if (root==NULL) return 0;
            
            if (root->left == NULL &&
                root->right == NULL &&
                i) {
                    return root->val;
                }
                
            int left = recur(root->left,1);
            int right = recur(root->right,0);
            
            return left+right;
        }
    };
    

    3ms solution
    Ok, so we can improve this by half the run-time by doing a couple improvements.

    Is there a better way of knowing if we are the left node?
    Lets think of this question a different way and say what if I could make a way where I never do recursion into a left leaf node?
    Ahh!! Smart! If we never need to go into a left leaf node, then we don't care if we are the left leaf node and we will assume we are either a parent of one/two children or the right node.
    If you were the parent of a left leaf node, why call a recursion method when I can just get it's value?
    This is precisely what happens here.
    If I am not a parent of a left leaf node continue recursion on both left and right children.
    But if I do find that I am a parent of the left leaf node, I will save its value and NOT continue recursion to the left side but continue recursion to the right.
    Ta Da!

    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if (root == NULL) return 0;
            int left = 0;
            if (root->left &&
                root->left->left == NULL &&
                root->left->right == NULL) 
            {
                    left = root->left->val;
            }
            else 
            {
                left = sumOfLeftLeaves(root->left);
            }
            int right = sumOfLeftLeaves(root->right);
            return left + right;
        }
    };
    

Log in to reply
 

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