一般我们二叉树遍历都是用递归，耗费内存但是快速且方便。
节省空间上来讲，迭代是个比较好的选择，由于需要保存层次节点（否则难以返回），所以我们可以用栈来辅助。
前序遍历，即先root再left再right，所以我们直接访问root，先压right，再压left完成本次操作。
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> rs=new ArrayList<Integer>(); if(root==null){ return rs; } Stack<TreeNode> st=new Stack<TreeNode>(); st.push(root); while(!st.empty()){ TreeNode t=st.pop(); rs.add(t.val); if(t.right!=null){ st.push(t.right); } if(t.left!=null){ st.push(t.left); } } return rs; } }顺便提一下：
中序，即先left，再root，再right，所以先压right，再压root，再压left，到达叶子节点再顺序弹出即可。
后序，即先left，再right，再root，所以先压root，再压right，再压left，到达叶子节点再顺序弹出即可，注意检查right子树。
节省栈空间上来讲，我们每一个节点如果左子树不为空，只压当前，不压右节点，直到本节点右子树也为空或已访问，才进行访问。这里注意，不需要检测左子树，因为左子树总是最先访问的。
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> rs=new ArrayList<Integer>(); Stack<TreeNode> s=new Stack<TreeNode>(); TreeNode pre=null; while(root!=null || !s.empty()){ //左子树访问 while(root!=null){ s.push(root); root=root.left; } root=s.pop(); //右子树检查 if(root.right==null || root.right==pre){ rs.add(root.val); pre=root; root=null; }else{ s.push(root); root=root.right; } } return rs; } }
这些还都再可以进行空间优化的...
