[recommend for beginners]concise & clean C++ implementation with detailed explaination


  • 2

    My first version implementation is not AC. The problem is that I use
    return when I call the sub-recursive-function.

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>>  result;
            vector<int> solution;
            help(root, sum, result, solution);
            return result;
        }
        
        void help(TreeNode* root, int sum, vector<vector<int>> &result, vector<int> solution){
            if(!root)   return;
            //leaf node
            if(!root->left && !root->right && root->val==sum) {
                solution.push_back(root->val);
                result.push_back(solution);
                return;
            }
            //not leaf node
            solution.push_back(root->val);
            if(root->left)  {
                //return  help(root->left, sum-root->val, result, solution);
                help(root->left, sum-root->val, result, solution);
            }
            if(root->right)  {
                //return  help(root->right, sum-root->val, result, solution);
                help(root->right, sum-root->val, result, solution);
            }
        }
    };

  • 0
    2
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> result;
            vector<int> path;
            help(root, result, path, 0, sum);
            return result;
        }
        
        void help(TreeNode* root, vector<vector<int>>& result, vector<int> path, int cur, const int& sum){
            if(!root)   return;
            cur += root->val;
            path.push_back(root->val);
            if(!root->left && !root->right) {
                if(cur == sum){
                    result.push_back(path);
                }
                return;
            }
            help(root->left, result, path, cur, sum);
            help(root->right, result, path, cur, sum);
            return;
        }
    };

Log in to reply
 

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