Simple top down DFS solution c++


  • 0
    S

    Simple top-down DFS solution, push and pop the neighboring nodes on the path.

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> result;
            if (!root) return result;
            vector<int> path;
            path.push_back(root->val);
            dfs(root, root->val, sum ,path, result);
            return result;
        }
        void dfs(TreeNode *root, int s, int sum, vector<int> &p, vector<vector<int>> &r) {
            if (!root) return;
            if (!root->left && !root->right) {
                if (s == sum) r.push_back(p);
                return;
            }
            
            if (root->left) {
                p.push_back(root->left->val);
                dfs(root->left, s+root->left->val, sum, p, r);
                p.pop_back();
            }
               
            if (root->right) {
                p.push_back(root->right->val);
                dfs(root->right, s+root->right->val, sum, p, r);
                p.pop_back();
            }   
        }
    };
    

Log in to reply
 

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