二叉树的前序、中序和后序遍历

给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
数据范围：0≤n≤1000，树上每个节点的val值满足 0≤val≤100
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

public int[][] threeOrders (TreeNode root) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        preOrder(root,list1);
        inOrder(root,list2);
        postOrder(root,list3);
        int[][] res=new int[3][list1.size()];
        for(int i=0;i<list1.size();i++){
            res[0][i]=list1.get(i);
            res[1][i]=list2.get(i);
            res[2][i]=list3.get(i);
        }
        return res;
    }
    public void preOrder(TreeNode root,List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
    public void inOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }
    public void postOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
 }

public class ThreeOrdersIteration {
  ArrayList<Integer> list1=new ArrayList<>();
  ArrayList<Integer> list2=new ArrayList<>();
  ArrayList<Integer> list3=new ArrayList<>();
  //先序遍历
   public void preOrder(TreeNode root, ArrayList<Integer> list1) {
          //初始化一个栈
          Stack<TreeNode> stack = new Stack<>();
          //将根节点入栈
          TreeNode cur=root;
          //判断栈是否为空
          while (!stack.isEmpty()||cur!=null) {
              if(cur!=null){
                  list1.add(cur.val);
                  stack.push(cur);
                  cur=cur.left;
              }else{
                  cur=stack.pop();
                  cur=cur.right;
              }
          }
    }
   //中序遍历
  public void inOrder(TreeNode root,ArrayList<Integer> list2){
    //创建一个空栈
    Stack< TreeNode> stack =new Stack<>();
    //设置当前节点为根节点
    TreeNode cur=root;
    //判断栈是否为空或者当前节点是否为null
    while (!stack.isEmpty()||cur!=null) {
      //如果当前节点不为空，就加入栈中
      if (cur!=null) {
        stack.push(cur);
        //并且将当前节点设置为当前节点的左节点
        cur=cur.left;
      //如果当前节点为空，就进行弹栈操作
      }else {
        //将当前节点设置为弹出来的元素
        cur=stack.pop();
        //将元素值加入到链表中
        list2.add(cur.val);
        //将当前节点设置为当前节点的右节点
        cur=cur.right;
      }
    }
  }
  //后序遍历
  public void postOrder(TreeNode root ,ArrayList<Integer> list3){
    //创建一个空栈
    Stack<TreeNode> stack=new Stack<>();
    //将根节点设置为当前节点
    TreeNode cur=root;
    //循环判断栈是否为空或者当前节点是否为null
    while(!stack.isEmpty()||cur!=null){
      //如果当前节点不是空
      if (cur!=null) {
        //当前节点入栈
        stack.push(cur);
        //添加节点值
        list3.add(0,cur.val);
        //节点右移
        cur=cur.right;
      //节点是null
      }else {
        //栈顶元素出栈
        cur=stack.pop();
        //节点左移
        cur=cur.left;
      }
    }
  }
}

这是利用递归和迭代的思想来实现对二叉树的先序遍历、中序遍历和后序遍历。
递归的思想其实是隐藏着一个栈，而利用迭代就是将隐藏的栈显示出来了。递归比较难理解一点，但是代码更加简单，迭代代码多，但是更加容易理解。
先序迭代：先创建一个空栈，然后将当前节点设置为根节点，然后进入while循序，利用栈不为空或当前节点不为空节点一直循环，一次循环对当前节点进行if判断，如果当前节点不为空，就将当前的值加入到链表中，然后将当前节点入栈，将当前节点设置为当前节点的左节点。如果为空的话，就进行弹栈操作，并且将当前节点设置为当前节点的右节点。