力扣--二叉树的深度遍历
有人相爱，有人开车去看海，有人连力扣第一题都做不出来。哈哈哈，这是之前看到的听说在力扣第一题下面的评论，今天我们不做第一题，来看看那棵又大又高的树，计算机中的树跟我们生活中不一样，是倒着放的，根在上，叶子在最下面。那在计算机中有什么用呢？那就多了去了，数据的存储结构，文件目录的结构，常见的排序，我们在数据库中查找都是底层应用了树的结构，可以说非常重要了。而在笔试和面试中也是考察重点，我们今天先来看看树的遍历方式的前三种，先序，中序和后序遍历。
一般树都由根节点和子节点组成，先序遍历就是先访问根节点，再访问左子树，最后访问右子树；中序遍历就是，先访问左子树，再根节点，再右子树；后序就是先左子树，再右子树，最后根节点。所以可以看出我们说的前中后表示根节点的顺序，根节点第一个访问就是前序，以此类推。
1、二叉树的遍历解题思路：三部曲
1、确定递归函数的参数和返回值类型
2、确定终止条件
3、确定单层递归的逻辑：每一层递归该如何实现，即递归的是实现是在这一步进行的
二叉树的节点定义：
struct TreeNode
{
int val; //存储节点的值
TreeNode * left; //存储结点的左指针
TreeNode * right; //存储结点的右指针
TreeNode(int x):val(x),left(NULL),right(NULL){} //构造函数，初始化一个节点时，左右指针都为空
};
1.1 二叉树的前序遍历
方法一：递归的方法
class solution
{
public:
//解题思路：按照递归的三部曲来
//1、确定递归函数及参数，我们需要递归遍历节点就需要传入结点的信息，同时还需要一个数组来保存我们遍历的元素值
void traversal(TreeNode * cur,vector<int>&result) // 因为不需要返回值，所以返回类型为void
{
if(cur==NULL) //2、终止条件如果结点为空，说明树为空，直接返回，不需要遍历
{
return;
}
//不为空的话就执行下面的操作
result.push_back(cur->val); //将当前节点的元素值保存下来
traversal(cur->left,result); //3、遍历当前节点的左子树，这里就是陷入递归的步骤，函数自己调用自己
traversal(cur->right,result); //3、遍历当前结点的右子树，同上
}
vector<int>preorderTraversal(TreeNode * root)
{
vector<int>result; //创建一个数组来保存元素
traversal(root,result); //函数调用
return result;
}
}
方法二：迭代法
/**
* 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>preorderTraversal(TreeNode* root) {
vector<int>result; //创建数组存储遍历的值
stack<TreeNode*>st; //创建一个栈用来存储遍历的每一个树结点
if(root == nullptr)
{
return result; //当根节点为空时，直接返回，不再遍历
}
st.push(root); //将根节点压入栈中
while(!st.empty())
{
TreeNode * node = st.top(); //新建一个结点指向栈顶元素
st.pop(); //弹出栈顶元素
result.push_back(node->val); //将弹出去的栈顶元素的值保存到我们的结果文件里面
if(node->right)
{
st.push(node->right); //然后把刚才的节点的右子树结点放入栈，因为栈是先进后出
//所以，右节点先进去，再放入左节点，就可以得到中左右的顺序
}
if(node->left)
{
st.push(node->left);
}
}
return result;
}
};
总结：递归方法相对简单，迭代法需要利用一个栈来存储结点，一般笔试或者面试的时候都考察迭代法。
1.2 二叉树的中序遍历
方法一：递归
/**
* 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:
/*
方法一：递归，采用三部曲
*/
void traversal(TreeNode * cur,vector<int>&result)
{
if(cur==nullptr) //当前结点为空直接返回
{
return;
}
//不为空的话执行下面的操作
traversal(cur->left,result); //先访问左子树
result.push_back(cur->val); //再访问根节点
traversal(cur->right,result); //最后访问右子树
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>result;
traversal(root,result); //函数调用
return result;
}
};
方法二：迭代法
//方法二：迭代法
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*>st; //创建一个栈来存储结点
vector<int>result; //定义vector来存储最终的结果
TreeNode * cur = root; //定义一个结点指针指向根节点
/*
下面就是主要的思路：因为是中序遍历，所以先要遍历左子树，再遍历根节点，再遍历右子树，
所以需要一直找到最左边的那个结点，先遍历它，再一个一个结点递归，最后到右子树，就可以了
*/
while(cur!=NULL ||!st.empty()) //当结点不为空就一直遍历
{
if(cur != NULL) //如果当前节点不为空，就加入到栈中
{
st.push(cur);
cur=cur->left; //一直找左子树，即最底层，直到结点为空
}
else //即已经到了最下层的节点了，这时候需要对存储在栈中的元素进行处理
{
cur=st.top(); //指向栈顶元素
st.pop(); //出栈
result.push_back(cur->val);
cur=cur->right; //遍历右子树
}
}
return result;
}
总结：对于中序遍历就是先根据当前结点是否为空找到最左端的子树，再根据栈是否为空对每一个结点进行处理，当两者都能不满足条件的时候，就可以得到处理结果
1.3 二叉树的后序遍历
方法一：递归
/**
* 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:
/*
方法一：递归法，同样是三部曲
*/
void traversal(TreeNode * cur,vector<int>&vec)
{
if(cur==NULL)
{
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;
}
};
方法二：迭代法
分析：对于前序遍历，我们的遍历顺序是中左右，我们调换左右子树的遍历顺序就可以得到中右左，再对结果反转，就可以得到左右中，就得到后序遍历的算法
方法二：迭代法
*/
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode *>st;
vector<int>result;
if(root==NULL)
{
return result;
}
st.push(root);
while(!st.empty())
{
TreeNode * cur = st.top();
st.pop(); //将栈顶元素弹出
result.push_back(cur->val); //处理根节点
if(cur->left)
{
st.push(cur->left); //先将左节点放进去，后出来
}
if(cur->right)
{
st.push(cur->right); //后将右节点放进去，先出来
}
//此时的顺序是中右左
}
reverse(result.begin(),result.end()); //反转就可以得到中左右
return result;
}
总结：二叉树的前、中、后序三种遍历方式对于递归来说，采用的思路都是一致的，但是采用迭代法的话，就会存在差距，迭代法对于前序和后序遍历比较相似，相互反转即可，都是用栈来遍历；而对于中序比较麻烦，需要根据指针来遍历。