二叉树中序遍历非递归实现
近日在刷Leetcode中有一道题，让你用非递归的方法实现二叉树的先序和中序遍历，先序遍历好说，根左右的顺序，维护一个栈，每次pop栈顶元素，访问，然后将其右节点，左节点依次压入（注意顺序！倒着来），直到栈为空时便结束了遍历，而实现中序遍历的非递归时，便遇到了不小的问题。
首先我们先从中序遍历的递归写法看起，写段简单的伪代码
InorderTraversal(root){
If (root==null) return
Else{
InorderTraversal(root.left);
Visit(root);
InorderTraversal(root.left);
}
}
我们看个例子，有个二叉树如下：{1,2,3,4,5,#,#}
1
2 3
4 5
设想下在递归算法中，他的执行顺序，我们用简写it()来表示函数InorderTraversal(root),
It(1)压入，it(2)压入，it(4)压入，此时4.left为null，it(null)压入，满足递归出口！，return，执行visit(4),然后又是it(null)压入，所有的it（4）执行完毕，回溯到it（2）的visit（2)....
此时，我们大概理解了递归的调用顺序，尝试写写非递归的方法吧。
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<Integer>(); //用来存放结果
Stack<TreeNode> s=new Stack<TreeNode>();
TreeNode p=root;
while(s.size()!=0){
p=s.peek();//取出栈顶的元素，相当于递归操作
while(p!=null) {
p=p.left;//相当于递归中不断压入左孩子，直到空指针入栈，上例中就是1，2，4，null
s.push(p);
}
s.pop(); //相当于递归算法的递归出口，此时p一定等于null，我们把他弹出，就相当于递归算法中的If (root==null) return
if (!s.empty()){
p=s.pop();
result.add(p.val);//回溯到了之前那层！对应递归算法中Visit(root);
s.push(p.right); //相当于InorderTraversal(root.left);
}
}
return result;
}
}
一定要自己亲手尝试写一下！！ | 
转播
