网站建设 产品拍照,成都最新防疫政策,烟台网站排名seo,做问卷有哪些网站目录
题目#xff1a;剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣#xff08;Leetcode#xff09;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
写在最后#xff1a; 题目#xff1a;剑指 Offer …目录
题目剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣Leetcode
题目的接口
解题思路
代码
过啦
写在最后 题目剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣Leetcode 题目的接口
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorvectorint pathSum(TreeNode* root, int target) {}
};
解题思路
这道题我一看到题目
我立马就想到是dfs也就是深度优先搜索
思想就是递归搜索整个二叉树的每一个节点
记录将路径记录到数组中
求和计算每一个通向叶子节点的路径的节点和
然后与题目中给出的taget进行比较
如果已经走到叶子节点并且路径的节点和与taget相同
就将路径的记录塞进二维数组
然后退回到上一节点路径记录减一
以此类推。
最后返回二维数组即可。
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint v;vectorvectorint vv;//传一个sum用来计算路径的节点和void dfs(TreeNode* node, int target, int sum){//计算路径节点和sum node-val;//将路径记录v.push_back(node-val);//如果左孩子不为空继续搜索if(node-left){dfs(node-left, target, sum);}//如果右孩子不为空继续搜索if(node-right){dfs(node-right, target, sum);}//如果路径节点和与taget相等且已经走到了叶子节点if(sum target node-left nullptr node-right nullptr){//将成功匹配的路径值放进二维数组中vv.push_back(v);}//搜索退回上一级节点路径记录数组也删除最后一个节点的值v.pop_back();}vectorvectorint pathSum(TreeNode* root, int target) {//如果是空树就直接返回空数组if(!root){return vv;}//深度优先搜索dfs(root, target, 0);//返回符合条件的数组return vv;}
};
过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
