非递归前序遍历

// Time Complexity: O(n), n is the node number in the tree
// Space Complexity: O(h), h is the height of the tree

    public void preorderTraversal(TreeNode root) {

        if(root == null)
            return;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){  //一直向下遍历cur子树的左孩子，直到cur为空（最底层）
                visit(cur);
                stack.push(cur);
                cur = cur.left;
            }
            else{      // cur==null   向上回溯，到其父节点的右孩子，继续遍历
                cur = stack.pop();   //cur的父节点
                cur = cur.right;    
            }
        }
        
    }

非递归中序遍历

// Time Complexity: O(n), n is the node number in the tree
// Space Complexity: O(h), h is the height of the tree

    public void  inorderTraversal(TreeNode root) {

        if(root == null)
            return ;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()){

            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            else{
                cur = stack.pop();
                visit(cur);
                cur = cur.right;
            }
        }
      
    }

非递归后序遍历

// Using two stacks, Reverse Preorder Traversal!
// Time Complexity: O(n)
// Space Complexity: O(n)

    public void  postorderTraversal(TreeNode root) {

        if(root == null)
            return;

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> output = new Stack<>();

        stack.push(root);//根节点压栈

        while(!stack.empty()){

            TreeNode cur = stack.pop();
            output.push(cur.val);

            if(cur.left != null)
                stack.push(cur.left);
            if(cur.right != null)
                stack.push(cur.right);
        }

        while(!output.empty())
            visit(output.pop());
        
    }

层序遍历

public void levelOrder(Node root){

        if(root == null)
            return;

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            visit(cur);

            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.right);
        }
    }