给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
对于二叉树的中序遍历就是左中右，这么记住就行，前序后序就是把重放在前面和后面的区别，我们先把递归的方法看一下然后慢慢讲解。
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();dfs(res,root);return res;}void dfs(List<Integer> res, TreeNode root) {if(root==null) {return;}//按照 左-打印-右的方式遍历dfs(res,root.left);res.add(root.val);dfs(res,root.right);}
}递归的代码看着还是很简单其实重点就是def里面的三行理解，因为是从左开始打印，所以此时首先递归先遍历的就是左节点，也就是如图的dfs(res,root.left);左节点完之后就是此时的中，此时的中也就是此时的根节点，所以直接加入数组即可。
接下来就是我们需要重点讲解的非递归方法，我们这里用的是栈来存储相关结点
以下面的二叉树举例子
大致思路如图
具体解释如图之后也就是两个判断之间循环操作，代码如下:
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();TreeNode pre = null;while(root!=null) {//如果左节点不为空，就将当前节点连带右子树全部挂到//左节点的最右子树下面if(root.left!=null) {pre = root.left;while(pre.right!=null) {pre = pre.right;}pre.right = root;//将root指向root的leftTreeNode tmp = root;root = root.left;tmp.left = null;//左子树为空，则打印这个节点，并向右边遍历 } else {res.add(root.val);root = root.right;}}return res;}
}