c++ solution O(n) space complexity O(log n) (height of tree)


  • 0
    B
    class Solution {
        int count = 0;
    public:
        int pathSum(TreeNode* root, int sum) {
            vector<int> path;
            preOrder(root, sum, path);
            return count;
        }
        
        void preOrder(TreeNode* node, int sum, vector <int> &path) {
            
            if (!node) return;
    
            path.push_back(node->val);
            
            preOrder(node->left, sum, path);
            preOrder(node->right, sum, path);
    
            int temp=0;
            for(vector<int>::reverse_iterator it = path.rbegin(); it != path.rend(); ++it)
            {
                temp += *it;
                if(temp==sum) {
                    count++;
                }
            }
            path.pop_back();
        }
    
    };
    

Log in to reply
 

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