【LeetCode】剑指 Offer（17）

目录

题目：剑指 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:vector<vector<int>> 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:vector<int> v;vector<vector<int>> 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();}vector<vector<int>> pathSum(TreeNode* root, int target) {//如果是空树，就直接返回空数组if(!root){return vv;}//深度优先搜索dfs(root, target, 0);//返回符合条件的数组return vv;}
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。