剑指offer_二叉树和为某一个值的路径(栈保存路径，二叉树的前序遍历+表格模拟栈操作)

jlanglang 发布于2021-10-08 10:04 / 2572人阅读

摘要：在二叉树的三种遍历方式中先访问根节点为二叉树的前序遍历。其次考虑，题干要求返回的是二叉树节点路径，所以我们需要定义一个空间来存放路径。

原题链接

文章目录

- 思路
- C++代码

思路

首先：要求二叉树的每个节点上的值，一定需要遍历二叉树，并且要先访问根节点。在二叉树的三种遍历方式中先访问根节点为二叉树的前序遍历。题目要求打印路径，从根节点到最后的叶节点才是一条路径。

其次考虑，题干要求返回的是二叉树节点路径，所以我们需要定义一个空间来存放路径。

再考虑查找的过程，以上题为例子

操作	路径	节点路径和	目标值
入节点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<vector<int>>ret;    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {        if(root==nullptr)            return ret;        int SumStack=0;//记录路径的和        vector<int>Path;//存放路径        _FindPath(root,expectNumber,Path,SumStack);        return ret;    }private:    void _FindPath(TreeNode*root,int expectNumber,vector<int>&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();    }};

超融合服务器专线服务二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/121800.html

【剑指offer】让抽象问题具体化

摘要：假设压入栈的所有数字均不相等。注意这两个序列的长度是相等的思路借助一个辅助栈来存储数据。当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。若存在，左右子树，递归检测左右子树是否复合规范。 1.包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路 1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数...

Keagan 2019-08-23 15:15 评论0 收藏0
LeetCode通关：连刷三十九道二叉树，刷疯了！⭐四万字长文搞定二叉树，建议收藏！⭐

分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们收藏一下。二叉树基础二叉树是一种比较常见的数据结构，在开始刷二叉树...

honhon 2021-09-04 16:45 评论0 收藏0
PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
Java实现基本数据结构2（树）

摘要：实现基本数据结构栈，队列，链表这篇笔记侧重点二叉树的三种遍历前中后迭代非迭代代码重建二叉树的代码与分析和关于二叉树的题简单理解二叉查找树红黑树，的性质，实际用途。同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党以下是算法导论第十...

opengps 2019-08-14 12:06 评论0 收藏0
剑指offer_二叉树的打印合集(C++_上下打印.换行打印.之字打印_bfs+栈与队列+用表格模拟

摘要：队列存放的是树节点的指针，其类型为打印完这个节点后将队列中的这个节点指向的左右子树入队，再把这个节点指针出队。注意一定要在有左右子树的时候在进队。选择二维数组形式返回，数组内以一维数组的形式储存。一行数据出队完毕后为。 ...

glumes 2021-10-08 10:04 评论0 收藏0