/** 
     * 前序遍历递归解法：  
     * （1）如果二叉树为空，空操作  
     * （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 
     */ 
    public static void preorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        System.out.print(root.val + " ");  
        preorderTraversalRec(root.left);  
        preorderTraversalRec(root.right);  
    }  
       
    /** 
     *  前序遍历迭代解法1：用一个辅助stack，总是把右孩子放进栈 
     *  http://www.***.com/watch?v=uPTCbdHSFg4 
     */ 
    public static void preorderTraversal(TreeNode root) {  
        if(root == null){  
            return;  
        }  
           
        Stack<TreeNode> stack = new Stack<TreeNode>();      // 辅助stack  
        stack.push(root);  
           
        while( !stack.isEmpty() ){  
            TreeNode cur = stack.pop();     // 出栈栈顶元素  
            System.out.print(cur.val + " ");  
               
            // 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子  
            if(cur.right != null){  
                stack.push(cur.right);  
            }  
            if(cur.left != null){  
                stack.push(cur.left);  
            }  
        }  
    }  

前序遍历迭代法2：
while(root!=null){
　　while(root!=null){
　　　　systom.out.print(root);
　　　　stack.push(root);
　　　　root=root.left;
}
root=stack.pop();
while(root.right==null){
　　root=stack.pop();
}
root=root.right;
}

/** 
     * 中序遍历递归解法  
     * （1）如果二叉树为空，空操作。  
     * （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 
     */ 
    public static void inorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        inorderTraversalRec(root.left);  
        System.out.print(root.val + " ");  
        inorderTraversalRec(root.right);  
    }  
       
    /** 
     * 中序遍历迭代解法 ，用栈先把根节点的所有左孩子都添加到栈内， 
     * 然后输出栈顶元素，再处理栈顶元素的右子树 
     * http://www.***.com/watch?v=50v1sJkjxoc 
     *  
     * 还有一种方法能不用递归和栈，基于线索二叉树的方法，较麻烦以后补上 
     * http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ 
     */ 
    public static void inorderTraversal(TreeNode root){  
        if(root == null){  
            return;  
        }  
        Stack<TreeNode> stack = new Stack<TreeNode>();  
        TreeNode cur = root;  
           
        while( true ){  
            while(cur != null){     // 先添加一个非空节点所有的左孩子到栈  
                stack.push(cur);  
                cur = cur.left;  
            }  
               
            if(stack.isEmpty()){  
                break;  
            }  
                   
            // 因为此时已经没有左孩子了，所以输出栈顶元素  
            cur = stack.pop();  
            System.out.print(cur.val + " ");  
　（每个节点的下一个节点是这个节点的右节点的最左节点，右节点没有左节点就是右节点，没有右节点就是栈中弹出的节点）
            cur = cur.right;    // 准备处理右子树  
        }  
    }  
   
    /** 
     * 后序遍历递归解法  
     * （1）如果二叉树为空，空操作  
     * （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 
     */ 
    public static void postorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        postorderTraversalRec(root.left);  
        postorderTraversalRec(root.right);  
        System.out.print(root.val + " ");  
    }  
       
    /** 
     *  后序遍历迭代解法 
     *  http://www.***.com/watch?v=hv-mJUs5mvU 
     *   
     */ 
    public static void postorderTraversal(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
           
        Stack<TreeNode> s = new Stack<TreeNode>();      // 第一个stack用于添加node和它的左右孩子  
        Stack<TreeNode> output = new Stack<TreeNode>();// 第二个stack用于翻转第一个stack输出  

（从s弹出一个加入output,并把弹出的左右加入s,循环。）

s.push(root);  
        while( !s.isEmpty() ){      // 确保所有元素都被翻转转移到第二个stack  
            TreeNode cur = s.pop(); // 把栈顶元素添加到第二个stack  
            output.push(cur);         
               
            if(cur.left != null){       // 把栈顶元素的左孩子和右孩子分别添加入第一个stack  
                s.push(cur.left);  
            }  
            if(cur.right != null){  
                s.push(cur.right);  
            }  
        }  
           
        while( !output.isEmpty() ){ // 遍历输出第二个stack，即为后序遍历  
            System.out.print(output.pop().val + " ");  
        }  
    }  
   
    /** 
     * 分层遍历二叉树（按层次从上往下，从左往右）迭代 
     * 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点 
     * ，访问，若左子节点或右子节点不为空，将其压入队列 
     */ 
    public static void levelTraversal(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  
        queue.push(root);  
   
        while (!queue.isEmpty()) {  
            TreeNode cur = queue.removeFirst();  
            System.out.print(cur.val + " ");  
            if (cur.left != null) {  
                queue.add(cur.left);  
            }  
            if (cur.right != null) {  
                queue.add(cur.right);  
            }  
        }  
    }