二叉树的遍历
二叉树的表示
//Java

public class TreeNode{
    int val;
    Node left,right;
    public Node(int val){
        this.val=val;
    }
} 

前序遍历
递归方法

public static void preOrder1(TreeNode root){
    if(root == null)
        return;
    System.out.println(root.val);
    preOrder1(root.left);
    preOrder1(root.right);
}

非递归方法

public static void preOrder2(TreeNode root){
    Stack<TreeNode>  stack = new Stack<>();
    TreeNode node = root;
    while(node != null || !stack.empty()){
        if(node != null){
            System.out.println(node.val);
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();
            node = node.right;
        }
    }
}

中序遍历

public static void inOrder1(TreeNode root){
    if(root == null)
        return;
    inOrder1(root.left);
    System.out.println(root.val);
    inOrder1(root.right);
}

非递归方法

//非递归方法
public static void inOrder2(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode node= root;
    while(node != null || !stack.empty()){
        if(node != null){
            stack.push(node);
            node = node.left;
        }else {
            node = stack.pop();
            System.out.println(node.val);
            node = node.right;
        }
    }
}

后序遍历
递归方法

public static void postOrder1(TreeNode root){
    if(root == null)
        return;
    postOrder1(root.left);
    postOrder1(root.right);
    System.out.println(root.val);
}

非递归方法

/*
* 后续遍历
*/

public void lastOrder(Btree<T> root){
     Stack<Btree<T>> stack = new Stack<Btree<T>>();
     Btree<T> p = root;//保存当前节点
     Btree<T> q = null;//记录最后一个输出的节点，用于检验是不是根节点的右节点

     while(p != null || !stack.isEmpty()){
         //由根节点向下遍历，知道找到该根节点下的最后一个叶子节点
         while (p != null) {
             stack.push(p);//非叶子节点入栈
             p = p.left;//指向该节点的左孩子
         }

         //p为空，栈非空,说明遍历完了左孩子，处于叶子节点状态
         if (!stack.isEmpty()) {
             p = stack.pop();//栈顶出栈

             //因为如果该节点有右节点，肯定是先访问完右节点才开始访问跟节点的
             //p.right == null：表示没有右节点，可以直接访问根节点
             //p.right == q:刚访问完该节点右节点，则可以访问我该节点
             if (p.right == null || p.right == q) {
                 visitDate(p);//访问当前节点
                 q = p;//记录这个节点
                 p = null;
             }else{//开始遍历右孩子
                 p = p.right;
             }
         }
     }
 }

 public static void LevelorderTraversal ( TreeNode root )
 {
     LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
     TreeNode node = root;

     if ( node == null ) return; /* 若是空树则直接返回 */
     Q.offer(node);

     while ( !Q.isEmpty() ) {
         node = Q.poll();
         System.out.println( node.val ); /* 访问取出队列的结点 */
         if ( node.left != null )   Q.offer(node.left);
         if ( node.right != null )   Q.offer(node.right);
     }
}

//计算二叉树的深度

public static int level(BinTree root){
      if(root == null){
          return 0;
      }
       int left = level(root.leftChild)+1;
       int right = level(root.rightChild)+1;
      return  left > right? left : right;
      
  }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

  public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int[][] res = new int[3][3];
        
        res[0] = firstorderTraversal(root);
        
        res[1] = inorderTraversal(root);
        
        res[2] = postorderTraversal(root);
        return res;
    }
    
    // 后续
     public int[] postorderTraversal (TreeNode root) {
        // write code here  
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode lastNode = root;

        while(!stack.isEmpty() || p != null){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            p = stack.peek();
            if(p.right == null || p.right == lastNode){
                list.add(stack.peek().val);
                p = null;
                lastNode = stack.pop();
            } else{
                p = p.right;
            }
        }
        int[] res = new int[list.size()];
       
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
              System.out.println(res[i]);
        }
        return res;
    }
    
    // 前序
     public int[] firstorderTraversal (TreeNode root) {
        // write code here  
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null){
            
              while(p != null){
                list.add(p.val);
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                p = stack.pop();
                p = p.right;
            }
        }
        int[] res = new int[list.size()];
       
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
            System.out.println(res[i]);
        }
        return res;
    }
    
    
    // 中序
     public int[] inorderTraversal (TreeNode root) {
        // write code here  
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                list.add(stack.peek().val);
                p = stack.pop().right;
            }
        }
        int[] res = new int[list.size()];
       
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
              System.out.println(res[i]);
        }
        return res;
    }
}