给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
题目标签:Tree / Depth-first Search
题目链接:LeetCode / LeetCode中国
Language | Runtime | Memory |
---|---|---|
cpp | 8 ms | 1.4 MB |
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
static auto _ = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution {
public:
vector<vector<int>> res;
void dfs(TreeNode* node, int sum, vector<int>& path) {
if (!node) {
return;
}
if (sum == 0 && !node->left && !node->right) {
res.push_back(path);
return;
}
if (node->left) {
path.push_back(node->left->val);
dfs(node->left, sum - node->left->val, path);
path.pop_back();
}
if (node->right) {
path.push_back(node->right->val);
dfs(node->right, sum - node->right->val, path);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (!root) return res;
vector<int> path;
path.push_back(root->val);
dfs(root, sum - root->val, path);
return res;
}
};