关于二叉树的遍历讲得最好的还是wiki：
关于非递归版本，主要是在二叉树超级不平衡的情况下，有可能栈溢出。以下是我写得先序遍历非递归版本，应该是对的吧，没实际运行过，其实也不好写... 基本思路是用TreeNode * n去遍历，先左子树往下，完了pop出一个父节点，把自己变成右子树继续。所以Stack里存的其实是父节点的信息。以下是参考wiki百科的版本，栈用的很少，只推右子树。
public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode n = root; while (n!= null || !stack.empty()) { if (n != null) { ans.add(n.val); if (n.right != null) { stack.push(n.right); } n = n.left; } else { n = stack.pop(); } } return ans; } }