Description
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]
]
Explain
這道題跟path sum的思想基本一樣也糊。
這道題一看就是深度優(yōu)先搜索的問題了胀糜。題意很簡單枝嘶，就是從找一個條路苦锨，從根部到葉子贺氓，其中節(jié)點的值加起來等于給定的值。那就遍歷每個節(jié)點，每次到達一個新的葉子節(jié)點時，加上當前結(jié)點的值钢猛，看是否等于給定的值，如果是轩缤，那么就找到了命迈。如果不是，退回上一層繼續(xù)遍歷火的，直到遍歷完整個樹壶愤，如果還找不到，那就無解馏鹤。
不同的地方就是要求變了征椒，上一道是返回一個布爾值，這一道是所有返回符合條件的情況湃累。直接上代碼
Solution
/**
* 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 {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>>res;
vector<int>_res;
if (!root) return res;
dfs(res, root, sum, 0, _res);
return res;
}
void dfs(vector<vector<int>>& res, TreeNode* root, int sum, int _sum, vector<int> _res) {
if (root) {
_res.push_back(root->val);
_sum += root->val;
dfs(res, root->left, sum, _sum, _res);
dfs(res, root->right, sum, _sum, _res);
if(!root->left&&!root->right&&_sum == sum) res.push_back(_res);
}
}
};
