中卫网站推广服务长沙seo推广
写在前面
leetcode：94. 二叉树的中序遍历
递归：很简单，只需调换顺序。但不能死记硬背，递归的精髓在于只需要处理好边界条件，其他交给数学归纳法即可，不要一开始就深入递归，在脑袋想它每一步的步骤，这是错误的方法。
非递归：必会，因为面试考核不会只考你递归写法，非递归的话按照我的思路，前序和后序是一个解法，中序是一个解法，都很容易理解。
什么是前序、中序、后序
前中后体现在根的遍历时机。
前序：根 左子树 右子树
中序：左子树 根 右子树
后序：左子树 右子树 根
二叉树的结构
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;}
}递归
递归思路
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
前序+中序+后序
只需要调整`list.add(root.val);`代码的顺序即可，比如以下代码分别为前序和中序。
非递归
前序 + 后序
前序
先序：先压栈push头节点；然后下面步骤。
1）pop一个节点cur；
2）处理cur；
3）先push右节点，再push左节点（如果有的话）；
4）循环上3个步骤；
解释：
（1）为什么先入栈右节点，因为栈是先进后出，为了实现先遍历左节点的效果，需要左节点晚一些入栈。
（2）为什么不需要压栈根节点，因为所有的子树都会被用左右节点分解，这里根节点的概念也就是左右节点的概念了。
后序
改一下先序的代码即可，先序压栈是先右后左，颠倒一下，得到的遍历顺序就是 中右左，再result数组反转一下，就变成想要的 左右中。
中序
中序：不断把左边界压栈，没有了就穿到右边继续左边界。【因为所有的树都可以被左边界分解掉】左根右，右会被不断分解为左根右。
1）每棵子树整棵树左边界进栈，
2）依次弹出的过程中，打印，对弹出节点的右子树周而复始。
解释：
（1）为什么这里需要多加一个指针，因为先序、后序{ 处理 } 和{ 遍历 }的节点顺序是一致的，中序没办法，他是遍历到左下角才处理，无法灵敏控制达到这种效果，必须借助栈来暂存元素。（2）指针动向：
- 指针非空就压栈并往左，指针为空就出栈输出并往右【不管遍历到左节点还是右节点的指针为空，都是直接出栈输出】
- 弹出之后只需要指向他的右孩子即可。【左 根 右】