今天开始二叉树！！
二叉树的递归遍历和层序遍历是两种常见的遍历方法。
递归遍历（如前序遍历）通过递归函数实现，从根节点开始，首先访问根节点，然后递归访问左子树和右子树。代码通过检查节点是否为空，并按顺序将节点值添加到结果列表中。
层序遍历利用队列从根节点开始，逐层访问树的每一层节点。每层节点都被依次加入队列，并在访问时将其子节点加入队列，直至遍历完整棵树。
两种方法各有优势，递归遍历简单直观，而层序遍历适用于按层次处理树结构的问题。两种方法也都十分重要，需要熟记于心！
下面先开始说递归遍历：
想要写准递归，需遵循递归三部曲进行：
1. 确定递归函数的参数和返回值：确定哪些参数是递归过程中需要处理的，那么就在这个递归函数里加上这个参数，同时还要明确每次递归的返回值是什么类型，从而方便判断递归函数的整体返回类型。
2. 确定终止条件：操作系统也是用一个栈的结构来保存每一层递归信息，如果递归没有终止，操作系统的内存栈必然会溢出。
3. 确定单层的递归逻辑：确定每一层递归需要处理的信息，从而实现重复调用自己达到递归的目的。
接下来以前序遍历为例来说明“递归三部曲”：
- 确认递归函数的参数和返回值： 因为要打印前序遍历节点的数值，所以参数需要传入result数组用来存放节点的数值。同时每次递归要处理当前节点，因此节点也应当传入，除此之外就不太需要其他东西了。
public void preorder(TreeNode root, List<Integer> result)
- 确定终止条件：在本题中，自然是在节点一层层深挖时，遇到空节点的时候就该返回了，所以如果当前遍历的节点是空就应该直接返回。
if(root == null){
return;
}
- 确定单层递归的逻辑： 前序遍历是 中左右 的顺序，所以在单层递归时，是要先存中间的节点的值，再存左子节点，最后是右子节点。因此对于当前节点来说，就是先存自己的值，然后遍历左节点，最后遍历右节点。
result.add(root.val); // mid
preorder(root.left, result); // left
preorder(root.right, result); // right
具体题目及完整代码如下：
题目链接：144. 二叉树的前序遍历
题目链接：94. 二叉树的中序遍历
题目链接：145. 二叉树的后序遍历
/** //Java 递归遍历中的前序遍历preorder
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result){
if(root == null){
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
中序遍历主要是修改了方法中的添加节点值到数组的时机
class Solution { // Java 递归遍历中的中序遍历 inorder
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> result){
if(root == null){
return;
}
inorder(root.left,result);
result.add(root.val); // notice the timing for adding here
inorder(root.right, result);
}
}
后序遍历也是同样的道理，只是修改了result数组使用add方法添加节点的值的时机
class Solution { // Java 递归遍历中的后序遍历postorder
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> result){
if(root == null){
return;
}
postorder(root.left, result);
postorder(root.right, result);
result.add(root.val); // notice the add timing here
}
}
复杂度分析：
时间复杂度：O(n)。因为每个节点都会被访问一次，然后preorder会被调用一次。
空间复杂度：O(n)/O(log n)。空间复杂度基于递归调用栈的深度，最坏情况下栈的深度等于树的高度h。对于平衡二叉树，树高h大约是log n，所以最坏情况下空间复杂度为O(log n)；对于非平衡树，最坏情况下为链表形状的树，树高h = n，所以最坏情况下空间复杂度为O(n)。
中序遍历和后序遍历的代码与前序遍历相同，只是顺序问题，所以复杂度分析一样。
接下来说说迭代法（非递归）来实现二叉树的前中后序遍历：
首先是介绍思路上为什么迭代法可以实现：我们知道递归法是可以实现二叉树的遍历的（上文刚讲过），这种方式也被称为深度优先搜索(Depth-First Search, 简称DFS)，而递归的实现就是 每次递归调用都会把函数的局部变量、参数值和返回地址等信息压入调用栈中，然后等递归返回的时候，从栈顶弹出各项参数。因此我们可以使用栈来直接模拟这个递归的过程。
我们先看前序遍历，前序遍历是中左右，所以我们每次先处理中间节点，那就先把中间节点放入栈中，接下来是放右子节点，最后是放左子节点。这是因为栈的结构表现出先进后出的特点，所以先放右子节点后放左子节点 才能保证输出的顺序是 中左右。 完整代码如下：
// Java 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
复杂度分析：
时间复杂度：O(n)。 每个节点都被访问一次，并且每个节点都被压入、弹出栈一次
空间复杂度：O(n)/O(log n)。取决于树的形状、高度。道理同递归法。
后序遍历可以是在前序遍历的基础上稍作修改得到，这是因为只需调转while循环中的对于左右节点处理代码，结果就由 中左右 变成 中右左，然后此时再把结果使用reverse反转函数把结果反转后， 就会变成左右中，也就是我们需要的后序遍历了。完整代码如下：
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){ // switch
stack.push(node.left);
}
if (node.right != null){ // switch
stack.push(node.right);
}
}
Collections.reverse(result); // reverse function
return result;
}
}
复杂度分析同 上述的迭代法的 前序遍历。
最后是中序遍历，中序遍历不能 由 以上代码的基础上通过一些顺序上的变幻和一些额外方法的使用实现。这是因为刚刚前序遍历时，访问的节点和要处理的节点是同一个节点---都是中间节点。而中序遍历是 左中右，访问的是顶部节点，处理的是底部节点，换句话说就是他得先遍历到树左边的最底部才开始处理节点，因此造成访问节点和处理节点不统一的问题。
所以我们的处理方式是 保留刚才前序遍历的两个核心操作：访问，即遍历节点 和 处理，即将元素放入result数组中；同时借助指针的遍历来帮助访问节点，用栈来处理节点上的元素。 完整代码如下：
class Solution { // Java 中序遍历顺序: 左-中-右 入栈顺序： 左-右
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
复杂度分析同 上述的迭代法的 前序遍历。
接下来是层序遍历，顾名思义 就是要按照树的结构一层一层的遍历出结果。这种方式也被称为广度优先搜索(Breadth-First Search, 简称BFS)。
遇到这样的结构，我们需要使用 队列 来帮助我们解决问题。因为队列先进先出的特点符合我们一层一层遍历二叉树的性质。
题目链接：102. 二叉树的层序遍历
/** // Java 层序遍历
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
List<List<Integer>> resultList = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun02(root);
return resultList;
}
public void checkFun02(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new LinkedList<>();
int size = queue.size();
while(size > 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
size--;
}
resultList.add(list);
}
}
}
复杂度分析：
时间复杂度：O(n)。每个节点都会访问一次，且每个节点都会被加入和移除队列一次，所以是O(n).
空间复杂度：O(n)。空间复杂度主要取决于resultList的大小，和队列中的值。
队列中会存储当前层和下一层的节点，最坏情况下是处理满二叉树的时候，最后一层的元素约等于n/2.
resultList数组是存放结果的。因为要存放所有的结果，所以是O(n)。
所以综合一下，空间复杂度为O(n)。
