今天开始学习二叉树。
建议学习《大话数据结构》二叉树部分，并结合下方视频学习二叉树的多种遍历方法。
一.理论基础
关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。
一些同学用做了很多二叉树的题目了，可能知道前中后序遍历，可能知道层序遍历，但是却没有框架。
我这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
大家可以对着如下图，看看自己理解的前后中序有没有问题。
最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现我们后面都会讲的，这里大家先要清楚这些理论基础。
二.144二叉树的前序遍历
1.思路分析
简而言之,前序递归算法如下:
2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void preorder (struct TreeNode* root,int* result,int* returnSize){
if(root==NULL) return;
result[(*returnSize)++]=root->val;
preorder(root->left,result,returnSize);
preorder(root->right,result,returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int* result=(int*)malloc(sizeof(int)*2000);
*returnSize=0;
preorder(root,result,returnSize);
return result;
}三.94二叉树的中序遍历
1.思路分析
中序遍历的算法如下,和前序遍历算法仅仅是代码顺序的差异。
2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void inorder(struct TreeNode* root,int* result,int* returnSize){
if(root==NULL) return;
inorder(root->left,result,returnSize);
result[(*returnSize)++]=root->val;
inorder(root->right,result,returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=0;
int* result=(int*)malloc(sizeof(int)*2000);
inorder(root,result,returnSize);
return result;
}四.145二叉树的后序遍历
1.思路分析
同样道理，后序遍历中的那三行代码顺序如下：
2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void postorder (struct TreeNode* root,int* result,int* returnSize){
if(root==NULL) return;
postorder(root->left,result,returnSize);
postorder(root->right,result,returnSize);
result[(*returnSize)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=0;
int* result=(int*)malloc(sizeof(int)*2000);
postorder(root,result,returnSize);
return result;
}如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。
