Share my Recursive and Iterative (using stack & queue) C++ Solution


  • 0
    S
    //Solution 1 -- 6 ms 5.52%
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if(!root) return 0;
            int sum = 0;
            sumOfLeftLeaves(root, false, sum);
            return sum;
        }
        void sumOfLeftLeaves(TreeNode* root, bool ifLeft, int& sum){
            if(!root) return;
            if(!root->left && !root->right && ifLeft)
                sum += root->val;
            sumOfLeftLeaves(root->left, true, sum);
            sumOfLeftLeaves(root->right, false, sum);
        }
    };
    
    //Solution 2 -- 6 ms 5.52%
    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if(!root) return 0;
            if(root->left && !root->left->right && !root->left->left)
                return root->left->val + sumOfLeftLeaves(root->right);
            return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        }
    };
    
    //Solution 3 -- 6 ms 5.52%
    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if(!root) return 0;
            int sum = 0;
            stack<TreeNode*> stk;
            stk.push(root);
            while(!stk.empty()){
                TreeNode* cur =stk.top();
                stk.pop();
                if(cur->left && !cur->left->left && !cur->left->right)
                    sum += cur->left->val;
                if(cur->right) stk.push(cur->right);
                if(cur->left) stk.push(cur->left);
            }
            return sum;
        }
    };
    
    //Solution 4 -- 6 ms 5.52%
    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if(!root) return 0;
            int sum = 0;
            queue<TreeNode*> q;
            q.push(root);
            while(!q.empty()){
                TreeNode* cur =q.front();
                q.pop();
                if(cur->left && !cur->left->left && !cur->left->right)
                    sum += cur->left->val;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            return sum;
        }
    };

Log in to reply
 

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