剑指offerWeek4
周二:二叉树中和为某一值的路径
题目链接:二叉树中和为某一值的路径文章来源:https://www.toymoban.com/news/detail-791634.html
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
保证树中结点值均不小于 0
。
数据范围
树中结点的数量 [0,1000]
。
样例
给出二叉树如下所示,并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出:[[5,4,12,1],[5,6,6,5]]
AC代码
/**
* 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>> res; // 可以理解为全局变量,少传一个参数
vector<vector<int>> findPath(TreeNode* root, int sum) {
vector<int> path;
dfs(root, path, sum);
return res;
}
void dfs(auto root, auto path, int sum)
{
if (!root) return ;
sum -= root->val;
path.push_back(root->val);
if (!root->right && !root->left && !sum) res.push_back(path);
dfs(root->left, path, sum);
dfs(root->right, path, sum);
path.pop_back();
sum += root->val;
}
};
思路:
整体思路文章来源地址https://www.toymoban.com/news/detail-791634.html
非常标准的DFS
dfs()
{
- 判断是否达到终止条件
- 对当前位置进行标记(标记走过,或者计数累计,或者其他题目要求)
- 判断当前位置是否满足题目条件
- 回溯
}
到了这里,关于剑指offer题解合集——Week4day2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!