Simple C++ recurision, 20ms


  • 2
    G

    DFS traverse the Tree, when reach the leaf node, judge if it's the correct sum path.

    class Solution {
    public:
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            if(!root) return mRes;
            vector<int> vec;
            path(root, sum, vec);
            return mRes;
        }
    
        void path(TreeNode *root, int sum, vector<int>& vec) {
            vec.push_back(root->val);
            if (!root->left && !root->right) { //leaf
                if (sum == root->val) mRes.push_back(vec);
                vec.pop_back();
                return;
            }
            if (root->left) path(root->left, sum - root->val, vec);
            if (root->right) path(root->right, sum - root->val, vec);
            vec.pop_back();
        }
    
        vector<vector<int> > mRes;
    };

Log in to reply
 

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