关于二叉树的遍历讲得最好的还是wiki：

关于非递归版本，主要是在二叉树超级不平衡的情况下，有可能栈溢出。以下是我写得先序遍历非递归版本，应该是对的吧，没实际运行过，其实也不好写... 基本思路是用TreeNode * n去遍历，先左子树往下，完了pop出一个父节点，把自己变成右子树继续。所以Stack里存的其实是父节点的信息。以下是参考wiki百科的版本，栈用的很少，只推右子树。

public class Solution {	    public ArrayList
     
       preorderTraversal(TreeNode root) {	        ArrayList
      
        ans = new ArrayList
       
        ();	        Stack
        
          stack = new Stack
         
          ();	        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;	    }	}
         
        
       
      
     

其实还有一个更简单的版本，直接先把root.right推到栈里，然后root.left。但不知道为什么好像没有上面那个版本流行。大概如下，没有实际运行过。参考：

public class Solution {    public ArrayList
     
       preorderTraversal(TreeNode root) {    	ArrayList
      
        ans = new ArrayList
       
        ();        Stack
        
          stack = new Stack
         
          ();        stack.push(root);        while (!stack.empty()) {        	TreeNode n = stack.pop();        	if (n != null) {        		ans.add(n.val);        		stack.push(n.right);        		stack.push(n.left);        	}        }        return ans;    }}