Path Sum II --路径和（重）-白红宇

Path Sum II --路径和（重）

阅读量：4108 次

发布时间：2019-05-25

本文共 1066 字，大约阅读时间需要 3 分钟。

问题：

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

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]]

解答：

上一题path sum的升级，多加一个记录路径的变量。

但是如果我没做上一题，直接做这一题的话，可能会采取先记录路径，再求和的方法，显然笨拙了很多。

代码：

class Solution {public:    vector
   
    
      > pathSum(TreeNode *root, int sum) {        vector
     
      
        > re_list;		vector
       
         result;		DFS(root, 0, sum, result, re_list);		return re_list;    }	void DFS(TreeNode *root, int sum, int target, vector
        
          result, vector
         
          
            > &re_list) { if(root == NULL) return; if(root->left == NULL && root->right == NULL) { if(target == root->val + sum) { result.push_back(root->val); re_list.push_back(result); } } else { result.push_back(root->val); DFS(root->left, sum+root->val, target, result, re_list); DFS(root->right, sum+root->val, target, result, re_list); } }};