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

想得到ArrayList的元素可以 .get(i)

import java.util.*;
//递归的方法pre mid post
/*
 * 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 ArrayList<Integer> first = new ArrayList<>();
       //中序
        public ArrayList<Integer> middle = new ArrayList<>();
       //后序
        public ArrayList<Integer> then = new ArrayList<>();
        // write code here
    public int[][] threeOrders (TreeNode root) {
        // write code here
        //关键点
        //1.确定存储数组大小 OR 使用 ArrayList
        //2.前中后遍历算法
        //3.ArrayList 数组转 int[] 数组方法
        firstOrder(root);
        middleOrder(root);
        thenOrder(root);
        //得到结果的二维数组
        int[][] result = new int[3][first.size()];
        result[0]=toIntArray(first);
        result[1]=toIntArray(middle);
        result[2]=toIntArray(then);
        //不能用ArrayList的原因是题目给的是int[][]
        //ArrayList a = new ArrayList();
        //a.add(first);
        //a.add(middle);
        //a.add(then);
        return result;
 
    }
    //ArrayList 转 int[]
    public int[] toIntArray(ArrayList<Integer> list){
        if(list==null||list.size()<1){
            return new int[0];
        }
        int[] result=new int[list.size()];
        for(int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        return result;
    }
 
    //先序遍历
    public void firstOrder(TreeNode root){
        //跳出条件
        if(root==null){
            return;
        }
        first.add(root.val);
        firstOrder(root.left);
        firstOrder(root.right);
 
    }
 
    //中序遍历
    public void middleOrder(TreeNode root){
        //跳出条件
        if(root==null){
            return;
        }
        middleOrder(root.left);
        middle.add(root.val);
        middleOrder(root.right);
 
    }
 
    //后序遍历
    public void thenOrder(TreeNode root){
        //跳出条件
        if(root==null){
            return;
        }
        thenOrder(root.left);
        thenOrder(root.right);
        then.add(root.val);
    }
    
}