LeetCode113 Path Sum II

题目链接

https://leetcode.com/problems/path-sum-ii/

题目描述

给你一个树和一个sum，找出来从根结点到叶子结点所有路径中路径之和等于sum的路径。

例如：
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]

题目分析

水题，DFS从根结点往下找，当为叶子结点，且curSum==sum的时候，找到一条路径。需要注意的是，sum可以为负值。

代码：

class Solution {
public:
    vector<vector<int>> paths;
    vector<int> v;
    void path(TreeNode* root,int curSum,int sum){
        if(root->left==NULL && root->right==NULL && curSum==sum){
            paths.push_back(v);
            return;
        }
        if(root->left!=NULL){
            int val=root->left->val;
            curSum+=val;
            v.push_back(val);
            path(root->left,curSum,sum);
            curSum-=val;
            v.pop_back();
        }
        if(root->right!=NULL){
            int val=root->right->val;
            curSum+=val;
            v.push_back(val);
            path(root->right,curSum,sum);
            curSum-=val;
            v.pop_back();
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(root==NULL){
            return paths;
        }
        else{
            v.push_back(root->val);
            path(root,root->val,sum);
            return paths;
        }
    }
};