题解 | #实现二叉树先序，中序和后序遍历#

方法一（栈）

1.题意整理

• 给定一颗二叉树。
• 按照先序、中序、后序打印二叉树中所有的节点。

2.思路整理

简单分析：先序遍历的顺序是根、左、右，中序遍历的顺序是左、根、右，后序遍历的顺序是左、右、根。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。

比如先序遍历：

	ArrayList<Integer> pre=new ArrayList<Integer>();

	private void preorder(TreeNode root){
        if(root==null) return;
        //加入到序列
        pre.add(root.val);
        //往左子树方向遍历
        preorder(root.left);
        //往右子树方向遍历
        preorder(root.right);
    }

所以，我们可以尝试使用迭代的方式来进行树的遍历。下面分别是利用栈进行先序、中序和后序遍历的思路。

先序遍历：将根节点作为起点节点，如果当前节点不为空，不断将它以及它的左子节点入栈。入栈之前就将节点加入到pre序列，所以遵循根、左的顺序。如果节点为空的时候，说明是最后一个左子节点，此时需要往右子树方向遍历。

图解展示：

中序遍历：将根节点作为起点节点，如果当前节点不为空，不断将它以及它的左子节点入栈。如果节点为空的时候，说明是最后一个左子节点，此时逐个将栈中元素出栈，加入到in序列。由于栈是先进后出结构，所以当前顺序一定是左、根。此时需要往右子树方向遍历。

图解展示：

后序遍历：将根节点作为起点节点，如果当前节点不为空，不断将它以及它的右子节点入栈。入栈之前就将节点加入到last序列，所以遵循根、右的顺序。如果节点为空，说明是最后一个右子节点，此时需要往左子树方向遍历。最后last序列存的是根、右、左顺序的节点，反转一下就变为后序遍历的左、右、根顺序。

图解展示：

3.代码实现

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整型二维数组
     */
    //记录先序序列
    ArrayList<Integer> pre=new ArrayList<Integer>();
    //记录中序序列
    ArrayList<Integer> in=new ArrayList<Integer>();
    //记录后序序列
    ArrayList<Integer> last=new ArrayList<Integer>();
    
    public int[][] threeOrders (TreeNode root) {
        //分别进行先序、中序和后序遍历
        preorder(root);
        inorder(root);
        lastorder(root);
        int[][] res=new int[3][];
        //将对应的序列转换为数组，存到结果集中
        res[0]=listtoArray(pre);
        res[1]=listtoArray(in);
        res[2]=listtoArray(last);
        return res;
    }
    
    //list转数组
    private int[] listtoArray(ArrayList<Integer> list){
        int[] arr=new int[list.size()];
        for(int i=0;i<list.size();i++){
            arr[i]=list.get(i);
        }
        return arr;
    }
    //中序遍历
    private void inorder(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        //新建栈
        LinkedList<TreeNode> s=new LinkedList<>();
        while(!s.isEmpty()||node!=null){
            //如果当前节点不为空，不断将它以及它的左子节点入栈
            if(node!=null){
                s.push(node);
                node=node.left;
            }
            else{
                node=s.pop();
                //由于栈是先进后出结构，所以当前顺序一定是左、根
                in.add(node.val);
                //往右子树方向遍历
                node=node.right;
            }
        }
    }
    //先序遍历
    private void preorder(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        //新建栈
        LinkedList<TreeNode> s=new LinkedList<>();
        while(!s.isEmpty()||node!=null){
            //如果当前节点不为空，不断将它以及它的左子节点入栈
            if(node!=null){
                s.push(node);
                //直接将节点加入到pre中，顺序是根、左
                pre.add(node.val);
                node=node.left;
            }
            else{
                node=s.pop();
                //往右子树方向遍历
                node=node.right;
            }
        }
    }
    //后序遍历
    private void lastorder(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        //新建栈
        LinkedList<TreeNode> s=new LinkedList<>();
        while(!s.isEmpty()||node!=null){
            //如果当前节点不为空，不断将它以及它的右子节点入栈
            if(node!=null){
                s.push(node);
                //直接将节点加入到last中，顺序是根、右
                last.add(node.val);
                node=node.right;
            }
            else{
                node=s.pop();
                //往左子树方向遍历
                node=node.left;
            }
        }
        //遍历完之后，序列遵循根、右、左的顺序，反转一下则变为左、右、根的顺序，即后序遍历
        Collections.reverse(last);
    }
    
}

4.复杂度分析

• 时间复杂度：不管哪种遍历方式都需要遍历树中所有节点，所以时间复杂度也是$O(n)O(n)$。
• 空间复杂度：需要深度不超过n的栈，所以空间复杂度为$O(n)O(n)$。