LeetCode|剑指offer_二叉树和为某一个值的路径(栈保存路径，二叉树的前序遍历+表格模拟栈操作) 数据结构|算法|数据结构与算法

原题链接

文章图片

文章目录

- 思路
- C++代码

思路首先：要求二叉树的每个节点上的值，一定需要遍历二叉树，并且要先访问根节点。在二叉树的三种遍历方式中先访问根节点为二叉树的前序遍历。题目要求打印路径，从根节点到最后的叶节点才是一条路径。
【LeetCode|剑指offer_二叉树和为某一个值的路径(栈保存路径，二叉树的前序遍历+表格模拟栈操作)】其次考虑，题干要求返回的是二叉树节点路径，所以我们需要定义一个空间来存放路径。
再考虑查找的过程，以上题为例子

操作	路径	节点路径和	目标值
入节点10	10	10	22
入节点5	10 5	15	22
入节点4	10 5 4	19	22
路径和！=目标值回到节点5
删除路径4	10 5	15	22
入节点7	10 5 7	22	22
路径和与目标值相同记录这个路径

根据上表分析储存路径的数据结构为后进先出的形式，所以用栈来存储。
返回形式
题目最后要求以二维数组的形式返回路径，所以我们用数组来存储路径，只要每次尾插数据，尾删数据，数组也可以看作为栈，当数组路径和与设置的相同时尾插到这个二维数组上。并且因为要以递归的形式来遍历二叉树，所以我们把二维数组定义为全局的形式，避免多次递归带来的性能损耗
我们在做这种递归的题的时候要想清楚三步
1.递归出口。2.子步骤要执行什么。3.递归条件与路径
1.递归出口：左右子树为空时(叶子节点)，这时还要判断路径和与设定值是否相同，结束后还要退回上一个节点，所以还要把这个节点踢出数组。
2.子步骤：每次递归到这个节点时要把这个节点的值加到记录路径和的变量中，同时还要把这个节点的数字尾插到数组上
3.递归条件与路径：二叉树的先序遍历，递归时当左树不为空时先递归左树。在左树为空后再递归右树
之后再以合理的方式将这三步组织起来
C++代码

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution {public: vector>ret; vector > FindPath(TreeNode* root,int expectNumber) {if(root==nullptr) return ret; int SumStack=0; //记录路径的和 vectorPath; //存放路径 _FindPath(root,expectNumber,Path,SumStack); return ret; } private: void _FindPath(TreeNode*root,int expectNumber,vector&Path,int SumStack) {SumStack=SumStack+root->val; //子步骤 Path.push_back(root->val); if(root->left)//递归路径与递归条件 {_FindPath(root->left,expectNumber,Path,SumStack); } if(root->right) {_FindPath(root->right,expectNumber,Path,SumStack); } //递归出口，在叶子节点要和规定值做对比，相同时尾插到全局的二维数组中 if(SumStack==expectNumber&&root->left==nullptr&&root->right==nullptr)//叶子节点且有相等的值 {ret.push_back(Path); } Path.pop_back(); } };