递归应该最常用的算法，相信大家都了解，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。代码如下：
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper(root, res);
return res;
}
private void helper(TreeNode root, ArrayList<Integer> res)
{
if(root == null)
return;
helper(root.left,res);
res.add(root.val);
helper(root.right,res);
}接下来是迭代的做法，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。过程中维护一个node表示当前走到的结点（不是中序遍历的那个结点），实现的代码如下：public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty())
{
if(root!=null)
{
stack.push(root);
root = root.left;
}
else
{
root = stack.pop();
res.add(root.val);
root = root.right;
}
}
return res;
}最后我们介绍一种比较复杂的方法，这个问题我有个朋友在去google
onsite的时候被问到了，就是如果用常量空间来中序遍历一颗二叉树。这种方法叫 Morris Traversal。想用O(1)空间进行遍历，因为不能用栈作为辅助空间来保存付节点的信息，重点在于当访问到子节点的时候如何重新回到父节点（当然这里是指没有父节点指针，如果有其实就比较好办，一直找遍历的后驱结点即可）。Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null)
{
if(cur.left == null)
{
res.add(cur.val);
cur = cur.right;
}
else
{
pre = cur.left;
while(pre.right!=null && pre.right!=cur)
pre = pre.right;
if(pre.right==null)
{
pre.right = cur;
cur = cur.left;
}
else
{
pre.right = null;
res.add(cur.val);
cur = cur.right;
}
}
}
return res;
}接下来我们来分析一下时间复杂度。咋一看可能会觉得时间复杂度是O(nlogn)，因为每次找前驱是需要logn，总共n个结点。但是如果仔细分析会发现整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，而n个结点的二叉树中有n-1条边，所以时间复杂度是O(2*n)=O(n)，仍然是一个线性算法。空间复杂度的话我们分析过了，只是两个辅助指针，所以是O(1)。Binary Tree Inorder Traversal -- LeetCode,布布扣,bubuko.com
Binary Tree Inorder Traversal -- LeetCode
原文：http://blog.csdn.net/linhuanmars/article/details/20187257