Easy to understand DFS solution C++


  • 0
    C

    This probably doesn't have the best time complexity (not too bad, AC 26ms) but extends trivially from the traditional DFS algorithm. We record the path when we visit the binary tree inorderly. At each node, we count the number of paths that ends with that node.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        void dfs(vector<int>& path,TreeNode* root,int& tsum,int& sum,int &count){
            if( !root ) return;
            path.push_back(root->val);
            tsum += root->val;
            int lsum = tsum;
            for(int i=0;i<path.size();i++){
                if( lsum == sum ) count++;
                lsum -= path[i];
            }
            if( root->left ){
                dfs(path,root->left,tsum,sum,count);
            }
            if( root->right ){
                dfs(path,root->right,tsum,sum,count);
            }
            tsum -= root->val;
            path.pop_back();
        }
    public:
        int pathSum(TreeNode* root, int sum) {
            vector<int> path;
            int count=0;
            int tsum=0;
            dfs(path,root,tsum,sum,count);
            return count;
        }
    };
    

Log in to reply
 

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