第94题：二叉树的中序遍历
一． 问题描述
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
二． 解题思路
本体思路：采用迭代的方法对二叉树进行遍历。
步骤一：建立一个空栈和一个list表，将temp节点指向根节点。
步骤二：判断temp是否为空？否则将根节点入栈，并将temp指向根节点的左子节点。（重复直到找到最左子节点）
步骤三：栈中取出最新节点，将数值记录下来，将temp指向该节点的右子节点，返回步骤二。
步骤四：知道栈为空，则遍历结束，将数值结果输出。
三． 执行结果
执行用时 :1 ms, 在所有 java 提交中击败了96.10%的用户
内存消耗 :34.8 MB, 在所有 java 提交中击败了39.36%的用户
四． Java代码
class Solution { public List<Integer> inorderTraversal(TreeNode root) { TreeNode temp=root; List<Integer> result=new ArrayList<Integer>(); List<TreeNode> zhan=new ArrayList<TreeNode>(); while(true){ if(temp!=null){ zhan.add(temp); temp=temp.left; }else if(zhan.size()>0) { int data=zhan.get(zhan.size()-1).val; result.add(data); temp=zhan.get(zhan.size()-1).right; zhan.remove(zhan.size()-1); }else { break; } } return result; } }