算法练习第13天|递归实现 144.二叉树的前序遍历(opens new window)145.二叉树的后序遍历(opens new window)94.二叉树的中序遍历
二叉树的存储
二叉树的存储方式：链式存储和顺序存储。链式存储用指针，顺序存储用数组。其结构如下图所示。
链式存储：
顺序存储：
顺序存储时，若父节点下表为i，则其左孩子下标为 2*i + 1，右孩子下标为2*i + 2.
二叉树的遍历方式
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
参考下图中二叉树的三种遍历结果来理解遍历过程。
做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
链式存储二叉树的节点实现
struct TreeNode{
int val; //元素值
TreeNode* left; //指向左孩子
TreeNode* right; //指向右孩子
//列表法表示构造函数
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};链式二叉树的递归遍历
每次写递归，都可以参考下面的递归三要素来写，提高代码的正确率！
-
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
-
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
下面我们的需求是用前、中、后序三种遍历方式的递归实现来获取各个节点的元素值，用vector来存放。
1.前序遍历递归函数实现 对应力扣链接144. 二叉树的前序遍历 - 力扣（LeetCode）
https://leetcode.cn/problems/binary-tree-preorder-traversal/
首先递归的第一个要素：确认递归函数的参数和返回值。
参数要包含一个节点指针，用于表示遍历到了当前节点。其次，对于遍历出来的元素值，用vector存起来，所以另一个参数是vector的引用。其他就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：
void traversal(TreeNode* cur, vector<int> &vec)第二要素：确认递归终止条件
在递归的过程中，什么时候本层递归结束？注意是本层递归。就是指向当前节点的cur指针为nullptr，表示当前节点为空，那么直接return，结束本层递归。
if(cur == nullptr) return;第三要素：确认单层递归的任务逻辑
针对我们要获取元素值的需求，首先我们要当前节点的元素值cur->val存放到vector中（因为是前序遍历，中左右，此时为中），然后将指向左孩子的指针作为递归函数的指针实参，对整个左子树进行遍历，最后将指向右孩子的的指针为递归函数的指针实参，对整个右子树进行遍历。
vec.push_back(cur->val);
traversal(cur->left, vec);
traversal(cur->right, vec);整体代码如下：
class Solution {
public:
//递归函数
void traversal(TreeNode* cur, vector<int>& vec) {
if(cur == nullptr) return;
vec.push_back(cur->val); //中
traversal(cur->left, vec); //左
traversal(cur->right, vec); //右
}
//利用递归函数完成前序遍历函数的封装，传入节点为根节点
vector<int> PreOrderTraversal(TreeNode * root){
vector<int> result;
traversal(root, result); //从根节点开始遍历
return result;
}
};2.中序遍历的递归函数
//递归函数
void traversal(TreeNode* cur, vector<int>& vec) {
if(cur == nullptr) return;
traversal(cur->left, vec); //左
vec.push_back(cur->val); //中
traversal(cur->right, vec); //右
}对应力扣94二叉树的中序遍历代码：
class Solution {
public:
//递归函数
void traversal(TreeNode* cur, vector<int>& vec) {
if(cur == nullptr) return;
traversal(cur->left, vec); //左
vec.push_back(cur->val); //中
traversal(cur->right, vec); //右
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};3.后序遍历的递归函数
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return; //先写本次递归的终止条件
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中
}对应力扣145.二叉树的后序遍历代码：
class Solution {
public:
void traversal(TreeNode * cur, vector<int> &vec){
//本层递归终止条件
if(cur==nullptr) return;
traversal(cur->left, vec); //左
traversal(cur->right, vec); //右
vec.push_back(cur->val); //中
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result ;
traversal(root, result);
return result;
}
};原文地址：https://blog.csdn.net/Brillian123/article/details/135775622
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！