Share my 18ms C++ solution


  • 1
    R

    The solution is simple DFS by passing in a vector for current branch solution and a 2D vector recording all solutions by reference. A possible improvement of the algorithm is we could terminate the recursion when (curSum < 0), provided all treeNode elements are positive.

    class Solution {
        public:
            void getSol(TreeNode *curNode, int curSum, vector<int>& curBranch, vector<vector<int> >& sol)
            {
                curBranch.push_back(curNode->val);
                
                // if curNode is a leaf node
                if (!curNode->left && !curNode->right && curNode->val == curSum)
                    sol.push_back(curBranch);
        
                if (curNode->left)
                    getSol(curNode->left, curSum - curNode->val, curBranch, sol);
        
                if (curNode->right)
                    getSol(curNode->right, curSum - curNode->val, curBranch, sol);
        
                curBranch.pop_back();
                return;
            }
            vector<vector<int>> pathSum(TreeNode* root, int sum) {
                vector<int> singleBranch;
                vector<vector<int> > allSolutions;
                
                if (root)
                    getSol(root, sum, singleBranch, allSolutions);
                return allSolutions;
            }
        };

Log in to reply
 

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