你还没搞定二叉树遍历吗!(数据结构系列)
鉴于有很多关注我的小伙伴是考研并且学生党，今天我整理了一些关于数据结构树当中关于遍历的知识。
标语：学习就是一个不断复习的过程，领悟便可创新，多数令人逐渐遗忘~
二叉树的相关概念总结下来就是
二叉树是数据结构当中的重中之重。
二叉树是一个树形结构，该结构可以为空。
每个节点最多有两棵子树，且有左右之分。
作者所使用的语言是C++,其实是和C语言并没有什么太大的区别哦
首先看看二叉树的样子
弱覆盖
大家其实可以注意到，这个圈圈叫做节点，而除了根节点（最上面的节点）的 节点叫做叶子节点。
二叉树的基础操作有很多，我们在这里简单介绍一下，创建节点的操作。想要创建节点，就必须要知道他的结构体类型，data代表数据，也就是圈圈里的值（可以为任何类型），LeftChild 指向左节点的指针，RightChild 指向右节点的指针
typedef struct BinTreeNode{DataType data;struct BinTreeNode* LeftChild;struct BinTreeNode* RightChild;}BinTreeNode;//创建节点
创建节点的详细代码：
void BinTreeCreat_1(BinTreeNode** t)//记住我们传的是树根的地址，这个**你应该知道了奥{DataType item;scanf("%c", &item);if (item == '#'){*t = NULL;}else{*t = (BinTreeNode*)malloc(sizeof(BinTreeNode));assert(*t != NULL);(*t)->data = item;BinTreeCreat_1(&((*t)->LeftChild));BinTreeCreat_1(&((*t)->RightChild));}}
细心的你可以看到scanf语句，这个就代表输入，这样我们就可以指挥树创建成什么样子啦！我们规定输入#代表空值，也就是上一个节点没有左叶子或者右叶子。
下面才到了我们今天讨论的众点：二叉树的遍历
二叉树的遍历分为四种：我将给出两种不同的方法进行描述（递归与非递归方法），下面所有的代码都已经leetcode测试过并且AC超过90%，好几种代码已经超过100%。
注意：递归与非递归的代码基本都是相同的，大家理解之后，记住一个，其他的记住就方便多了。
层次遍历：就是按照每层的顺序，依次从左到右输出
二叉树的层次遍历/*** 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>> levelOrder(TreeNode* root) {vector<vector<int>>vec;//定义一个二维数组if(root == nullptr)return vec;//若树为空时，直接进行返回queue<TreeNode*>q; //借用队列先入先出的性质q.push(root);//先对根节点进行入栈vector<int> v_fir;while(!q.empty()){int sz = q.size();//取队列头部的元素的个数，也就是二叉树中某层元素的个数for(int i = 0;i < sz;i++){TreeNode *temp = q.front();q.pop();v_fir.push_back(temp->val); //先将二维数组每一行的值记录下来if(temp->left) q.push(temp->left);if(temp->right)q.push(temp->right);//将某节点的左右子树记录下}vec.push_back(v_fir);//将一维数组放入二维数组的每一行v_fir.erase(v_fir.begin(),v_fir.end());//再将一维数组清空，继续进行插入操作}return vec;}};
先序遍历：记住要点，根左右
思路与解析：先将根节点的值放入，然后递归左右子树，到空节点为止
代码一：递归方法/*** 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 dfs(TreeNode*root,vector<int>&v){if(root == nullptr)return ;//终止条件v.push_back(root->val);//dfs(root -> left,v);dfs(root->right,v);//递归左右子树}vector<int> preorderTraversal(TreeNode* root) {vector<int>v;dfs(root,v);return v;}};
代码二：非递归
思路与解析：
使用栈来模拟递归的操作：循环条件：节点不为NULL，且栈不为空。
若当前节点不为空，则访问该节点，将该节点入栈，不断递归左子树。
若左子树为空，则去寻找他的右子树，不断进行上述过程，直到所有节点全部遍历到（栈为空时）。
/*** 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>v;stack<TreeNode*>s;while(!s.empty()||root){while(root)//若当前节点不为空{v.push_back(root->val);//将当前节点的值入数组s.push(root);//将当前节点入栈root = root->left;//递归左子树}TreeNode*temp = s.top();s.pop();root = temp->right; //若左子树为空，便将节点指向右子树}return v;}};
中序遍历：记住要点:左根右
代码一：递归
思路与解析：先递归左子树，递归完左子树进行将值放入数组，递归右子树
/*** 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 dfs(TreeNode*root,vector<int> &v){if(root == nullptr)return ;if(root->left)dfs(root->left,v);v.push_back(root->val);if(root->right)dfs(root->right,v);}vector<int> inorderTraversal(TreeNode* root) {vector<int>v;dfs(root,v);return v;}};
代码二：非递归
思路与解析：和前序遍历类似，只不过访问节点从第一次进栈时变成出栈时访问节点。
/*** 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> inorderTraversal(TreeNode* root) {vector<int>v;stack<TreeNode*>s;while(!s.empty()||root){while(root){root = root->left;}s.push(root);TreeNode*temp = s.top();s.pop();v.push_back(temp->val);root = temp->right;}return v;}};
后序递归：记住要点：左右根
思路与解析：递归左右子树，然后记录其值
/*** 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 dfs(TreeNode* root,vector<int>&v){if(root == nullptr)return ;dfs(root->left,v);dfs(root->right,v);v.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int>v;dfs(root,v);return v;}};
代码二：非递归
思路与解析：后序遍历的难点在于第一次将根节点出栈后，并不能直接访问，必须访问其右子树后才可以。非递归后序遍历有很多种实现方式，我个人比较喜欢，使用一个状态栈来存储栈中元素的状态，状态为0暂时不可访问，状态为1可以访问。
/*** 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> postorderTraversal(TreeNode* root) {vector<int>v;stack<TreeNode*>s1;stack<int>s2;while(root||!s1.empty()){while(root){s1.push(root);s2.push(0);root = root->left;}TreeNode*temp = s1.top();cout<<temp->val<<endl;int flag = s2.top();if(flag == 0){root = temp->right;s2.pop();s2.push(1);}else if(flag == 1){v.push_back(temp->val);s1.pop();s2.pop();}}return v;}};