前言
对于数据结构其实一直有很大的兴趣，之前在面试的筹备过程中，陆陆续续刷过很多题，但是没有沉淀下来，所以从今年开始，准备系统的将自己学习的知识整理，作为自己的沉淀，也能和诸君分享所得。
万事要有一个开头，之所以选择了二叉树是因为二叉树基于基本数据结构，如数组，链表，栈，队列基础之上，可以将大部分的数据问题涵盖其中。多数的算法问题，如回溯，路径问题也都可以从二叉树基础上整理出一套方法论，所以就以此开始。
二叉树的三种遍历
首先学习一种数据结构，要先掌握这个数据结构的基本能力，比如数据结构的增删改查，而基于此之上，查询的能力毋庸置疑是curd的基础，那么本篇主要来介绍二叉树的遍历。
首先基于二叉树的定义
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点
由定义可推知，二叉树是具有天然的递归结构的，什么意思呢？
第一次接触递归的时候，大部分数据中的例子都是找盒子里的钥匙
首先你有一个盒子，需要你做的事情是从这个盒子里找到一把钥匙，然而盒子里可能没有钥匙，取而代之的可能是另外一个盒子。该怎么找到这把钥匙呢？
在这个盒子的问题中我们可以看到，大盒子里面的小盒子在处理的手段上其实是和大盒子一样的模式，打开每一个盒子我们都有两种结果，盒子里有钥匙，盒子里面有盒子。在小盒子里面找钥匙其实就是在大盒子里面找钥匙的本身。
所以，这个盒子就是我们的一个递归问题，我们递归的终点就是找到钥匙。那么盒子问题可以演化为
1、拆盒子。
2、找到钥匙停止下来。
由此具备了一个递归的条件
- 子问题须与原始问题为同样的事，且更为简单；
- 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在这里子问题就是盒子里的盒子，而终点就是我们的钥匙。再回头看我们二叉树的定义。二叉树每一个节点的左子树和右子树还是一颗二叉树（空树是特殊的二叉树），那么对于二叉树，之所以说满足天然的递归结构也是基于此。
1、二叉树的子树与二叉树是同样的结构，且更为简单。
2、二叉树的遍历终点既是空树。
由此，我们先尝试用递归来进行一次遍历二叉树吧~
首先，定义树的结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
接下来我们要清楚我们递归的重点，即当节点为空树时，不在遍历。
public void traversal(TreeNode node) {
if(node == null) {
return;
}
}
然后让我们开开心心的遍历出这颗二叉树，二叉树化成和二叉树本身一样，但是更简单的左子树和右子树
public void traversal(TreeNode node) {
if(node == null) {
return;
}
// 前序遍历
System.out.println(node.val);
traversal(node.left);
traversal(node.right);
// 中序遍历
traversal(node.left);
System.out.println(node.val);
traversal(node.right);
// 后序遍历
traversal(node.left);
traversal(node.right);
System.out.println(node.val);
}
顺带一提，对于二叉树来说的三种遍历模式也就如上，前序中序后续的差异就是把父节点是先看一下呢，还是在中间看一下呢，还是后看一下呢？本质上就是如此了，整理一下也就是
前序遍历：父节点->左子树->右子树
中序遍历：左子树->父节点->右子树
前序遍历：左子树->右子树->父节点
窃以为，之所以二叉树定义了这三种遍历的方式，就是从递归本身的方便性出发的，因为只需要调换一下递归单元中根节点的顺序，就可以得到三种遍历结果，毕竟如上面所说，二叉树是具有天然性质的递归结构嘛。
顺带一提，其实从二叉树的遍历中，我们也可以总结一下递归的注意点。
1、要知道什么时候结束递归。
2、每一个递归单元的形式是否一致。
之后在处理涉及递归的算法时，脑海中先把这两个问题想一下，对于算法的解题思路会清晰很多。
网友评论