Transparent C++ solution, 12ms, logarithmic time and space, reuse the same vector during recursion


  • 0
    X
    class Solution {
    public:
        int getMaxDepth(TreeNode* root)
        {
            if(root == nullptr)
            {
                return 0;
            }
            return 1 + max(getMaxDepth(root->left), getMaxDepth(root->right));
        }
    
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> paths;
            vector<int> p;
            p.resize(getMaxDepth(root));
            pathSumRecursive(root, sum, paths, p, 0);
            return paths;
        }
        
        void pathSumRecursive(TreeNode* root, int sum, vector<vector<int>>& paths, vector<int>& p, int level)
        {
            if(root == nullptr)
            {
                return;
            }
            p[level] = root->val;
            if(root->val == sum && root->left == nullptr && root->right == nullptr)
            {
                paths.push_back(vector<int>(p.begin(), p.begin() + level + 1));
                return;
            }
            pathSumRecursive(root->left, sum - root->val, paths, p, level + 1);
            pathSumRecursive(root->right, sum - root->val, paths, p, level + 1);
        }
    };

Log in to reply
 

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