Share my 18ms C++ solution

  • 1

    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 {
            void getSol(TreeNode *curNode, int curSum, vector<int>& curBranch, vector<vector<int> >& sol)
                // if curNode is a leaf node
                if (!curNode->left && !curNode->right && curNode->val == curSum)
                if (curNode->left)
                    getSol(curNode->left, curSum - curNode->val, curBranch, sol);
                if (curNode->right)
                    getSol(curNode->right, curSum - curNode->val, curBranch, sol);
            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.