递归：
// 下面是基本结构：
// 区别在于打印的位置不同
void preOrder(TreeNode root){
if(root == null) return;
if(root.left != null) preOrder(root.left);
if(root.right != null) preOrder(root.right);
}
//前序：
void preOrder(TreeNode root){
if(root == null) return;
System.out.println(root.val);
if(root.left != null) preOrder(root.left);
if(root.right != null) preOrder(root.right);
}
//中序：
void midOrder(TreeNode root){
if(root == null) return;
if(root.left != null) midOrder(root.left);
System.out.println(root.val);
if(root.right != null) midOrder(root.right);
}
//后序：
void postOrder(TreeNode root){
if(root == null) return;
if(root.left != null) postOrder(root.left);
if(root.right != null) postOrder(root.right);
System.out.println(root.val);
}
递归序：
二叉树.JPG
递归一个二叉树时，任意一个节点一定可以到达三次，这个顺序称为递归序。
例如：
1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
连续出现三个4：到达4，往左遍历为空，返回4，再往右遍历仍为空，再返回4
前序遍历：第一次到达节点就打印
中序遍历：第二次...
后序遍历：最后一次...
// 非递归版本（回去补，2021-04-19）
借助栈来实现（递归是栈的一种使用）
Stack<TreeNode> sk = new Stack<>();
前序：
- 先压入头结点
- 弹出一个节点，打印
- 依此压入所弹出节点的右节点和左节点（保证先左再右的顺序）
void preOrder(TreeNode root){
if(root == null) return;
Stack<TreeNode> sk = new Stack<>();
sk.push(root);
while(! sk.isEmpty()){
TreeNode t = sk.pop();
System.out.println(t.val);
// 先压右再压左
if(t.right != null) sk.push(t.right);
if(t.left !=null) sk.push(t.left);
}
}
后序：
刚刚前序的打印顺序为： 中--->左--->右
颠倒过来是：右--->左--->中
如果要满足后序遍历的 左右中 的顺序，那么在前序遍历时先压左再压右即可！
因此，需要再定义一个收集栈，用来反序
void postOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> sk = new Stack<>();
Stack<TreeNode> collectionSk = new Stack<>(); // 收集栈
sk.push(root);
while(!sk.isEmpty()){
TreeNode t = sk.pop();
collectionSk.push(t);
// 先左再右
if(t.left != null) collectionSk.push(t.left);
if(t.right != null) collectionSk.push(t.right);
}
// 打印收集栈
System.out.print(collectionSk);
}
中序：
（有点复杂，明天补）
