總結一下二叉樹的四種遍歷方式，用遞回和迭代，遞回代碼比較簡單，迭代代碼相對比較復雜點，

一.前序遍歷

（這里以列印出結果為例，還可以用ArrayList，存盤子樹中的val）

思路

遞回：先根節點，再左子樹，再右子樹，

迭代：需要使用到堆疊，先壓堆疊root，進入回圈（結束回圈條件為：堆疊空），再彈堆疊用top保留下來列印val，判斷top右子樹不為空，則壓堆疊，判斷top左子樹不為空，也壓堆疊（這兩個判斷順序不能改變），拿圖直觀理解一下，

代碼

遞回

public static void preOrder(Node root){
		//根節點為空，直接結束
        if(root==null){
            return;
        }
        //根節點
        System.out.print(root.val+" ");
        //左子樹
        preOrder(root.left);
        //右子樹
        preOrder(root.right);
}

迭代

  public static void preOrder(TreeNode root){
     //根節點為空，直接結束
      if(root==null){
          return;
      }
      Stack<TreeNode> s=new Stack<>();
      //先入堆疊
      s.push(root);
      while (!s.empty()){
          TreeNode top=s.pop();
          System.out.print(top.val+" ");
          //先右后左，順序不能亂
          if(top.right!=null){
              s.push(top.right);
          }
          if(top.left!=null){
              s.push(top.left);
          }
      }
  }

二.中序遍歷

思路

遞回：先根左子樹，再根節點，再右子樹，

迭代：cur=root，進入一個死回圈（里面有if判斷條件，堆疊空，則break）;
1.再進入一個回圈，cur不為空，則入堆疊，一直向左，入堆疊,直到左子樹為空，
2.判斷if，堆疊空則結束死回圈，
3.彈堆疊，列印，
4.cur=top.right，
重復上述操作

代碼

遞回

  public static void inOrder(Node root){
  		//根節點為空，直接結束
        if(root==null){
            return;
        }
        //左子樹
        inOrder(root.left);
        //根節點
        System.out.print(root.val+" ");
        //右子樹
        inOrder(root.right);

 }

迭代

public static void inOrder(TreeNode root){
		//根節點為空，直接結束
        if(root==null){
            return;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        while (true){
            //往左找，并且入堆疊
            while (cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            //堆疊為空，遍歷就結束
            if(s.empty()){
                break;
            }
            //取堆疊頂元素訪問
            TreeNode top=s.pop();
            System.out.print(top.val+" ");
            //從當前節點右子樹出發重復上面操作
            cur=top.right;
        }
 }

三.后序遍歷

思路

遞回：先根左子樹，再根右子樹，再根節點，

迭代：后序的思路和中序差不多，有一點區別在于，
取堆疊頂元素的時候此時是peek（），要看堆疊頂元素，是否有右子樹或者右子樹是否已經被訪問過了，當沒有右子樹，或者已經訪問過，則直接彈堆疊列印，
其余操作和中序一樣，看代碼就可以理解，

代碼

遞回

 public static void postOrder(Node root){
 		//根節點為空，直接結束
        if(root==null){
            return;
        }
        //左子樹
        postOrder(root.left);
        //右子樹
        postOrder(root.right);
        //根節點
        System.out.print(root.val+" ");
}

迭代

 public static void postOrder(TreeNode root){
 		//根節點為空，直接結束
        if(root==null){
            return;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (true){
            //往左找，并且入堆疊
            while (cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            //堆疊為空，遍歷就結束
            if(s.empty()){
                break;
            }
            //取出堆疊頂元素來看看能不能訪問
            TreeNode top=s.peek();
            //堆疊頂元素右子樹為空，或者已經被訪問過了
            if(top.right==null||top.right==prev){
                System.out.println(top.val+" ");
                s.pop();
                //保持好，prve為已經遍歷完的最后一個元素（這個細節很重要哦）用來判斷是否已經訪問過了
                prev=top;
            }else {
                cur=top.right;
            }
        }
}

四.層序遍歷

思路

遞回：以力扣的102題為例，
迭代：用佇列來操作，先入隊root，進入回圈（結束條件，佇列為空），
1.cur保存出隊元素，并列印val，
2.cur.left不為空，則入隊，
3.cur.right 不為空，則入隊，
重新操作回圈，直到佇列為空，結束回圈，

代碼

遞回

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        //根節點為空，直接結束
        if(root==null){
            return  result;
        }
        helper(root,0,result);
        return result;
    }

    private void helper(TreeNode root, int level,List<List<Integer>> result) {
        //當訪問的該行沒有在result中對應的時候，就加入一行
        if(level==result.size()){
            result.add(new ArrayList<>());
        }
        //get訪問到行，add添加元素val
        result.get(level).add(root.val);
        //訪問左邊
        if(root.left!=null){
            helper(root.left,level+1,result);
        }
        //訪問右邊
        if(root.right!=null){
            helper(root.right,level+1,result);
        }
    }

迭代

 public static void levelOrder(Node root){
 		//根節點為空，直接結束
        if(root==null){
            return;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur=queue.poll();
            System.out.print(cur.val+" ");
            //判斷左子樹
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            //判斷右子樹
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }