概述
关于二叉树，我们都不陌生，许多基于递归的问题发起点都是一个二叉树的root节点。对于各种二叉树的问题，我们也是通过dfs进行求解。例如求二叉树的深度、最近公共祖先等
算法分析
关于二叉树的中序遍历，我们都知道应该先访问最左边的节点，然后找到root根节点，再访问右节点。对应上图的二叉树，其中序遍历的结果应为：1 -> 2 -> 3 -> 4
算法编码
递归版本
- 递归的中序遍历写法较为简便，只需要通过inOrder方法写在打印根节点前后的位置即可
public void inOrder(TreeNode root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.value);inOrder(root.right);
}
非递归版本
- 中序遍历二叉树我们需要优先遍历左子树，然后才是根节点。但是根节点是优先于左子树被访问到的。这种反转的先后关系（先遍历、后打印），就需要借助栈（Stack）完成
如何给出遍历的条件终止和循环也是需要考虑的，我们知道，只要根节点的左子树持续存在，我们就应该先打印左子树的节点，因此这里的逻辑就变成下述代码：
while(cur != null ) {stack.push(cur);cur = cur.left;
}
- 如果是上面这种写法，当不存在左节点的时候，循环会跳出while部分，但是我们再取栈顶继续向后遍历的时候，依然要继续while的过程，因此我们的while条件就不能只是 cur的左子树不空，还应该加上当前栈内元素个数大于0
- 因此上面的代码可以改为：
while(cur != null || !stack.isEmpty()) {while(cur != null ) {stack.push(cur);cur = cur.left;}
}
- 如果cur没有左子树的情况下，我们正常执行出栈，即 stack.pop()，并打印出栈的元素。改造后的代码如下所示
while(cur != null || !stack.isEmpty()) {while(cur != null ) {stack.push(cur);cur = cur.left;}TreeNode top = st.pop();System.out.println(top.val);
}
- 如果有右子树的情况下，cur转换为右子树，继续上述过程
while(cur != null || !stack.isEmpty()) {if(cur != null ) {stack.push(cur);cur = cur.left;}cur = st.pop();//中序遍历的顺序结果打印System.out.println(cur.val);cur = cur.right;
}
算法总结
中序遍历在求解二叉树top-K问题的时候比较实用，可以直接通过打印、取值的情况下完成结果集的获取；如果求第k大或者第k小的元素，直接通过统计变量进行递减实现结果获取。希望大家都能清晰地掌握。
