Short 16ms C++ solution using recursion with brief explanation


  • 0
    D

    We have to consider whether each node has zero, two, or one children to make the recursive call. We store a current path path as well as the current sum num along the path, and the target sum sum.

    class Solution {
    public:
        void pathSumHelper(TreeNode* root, int num, int sum, vector<int>& path, vector<vector<int> >& result) {
            path.emplace_back(root->val), num += root->val;
            if (!root->left && !root->right) {
                if (num == sum) { result.emplace_back(path); }
            } else if (root->left && root->right) {
                pathSumHelper(root->left, num, sum, path, result), pathSumHelper(root->right, num, sum, path, result);
            } else {
                pathSumHelper(root->left ? root->left : root->right, num, sum, path, result);
            }
            path.pop_back();
        }
        
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            if (!root) { return {}; }
            vector<int> path;
            vector<vector<int> > result;
            pathSumHelper(root, 0, sum, path, result);
            return result;
        }
    };

Log in to reply
 

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