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

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
        //特殊值（空指针）处理
        if(root == null){
            return new int[3][0];
        }
        
        ArrayList<Integer> list = new ArrayList<>();//创建一个链表（无法确定二叉树节点的数量，不能创建数组）
        preOrder(root,list);//先序遍历
        int len = list.size();//确定二叉树节点的数量
        int[][] array = new int[3][len];//确定了二叉树节点的数量，创建二维数组
        Object[] obj = list.toArray();//链表转换为Object数组
        //Object数组转换为整形数组
        for(int i=0;i<len;i++){
            array[0][i] = (int)obj[i];
        }
        
        midOrder(root,array[1],0);//中序遍历
        afterOrder(root,array[2],0);//后序遍历
        
        return array;
    }
    
    //先序遍历
    public void preOrder(TreeNode root,ArrayList<Integer> list){
        //递归出口
        if(root == null){
            return ;
        }
        
        list.add(root.val);//遍历根节点
        preOrder(root.left,list);//递归左子树
        preOrder(root.right,list);//递归右子树
    }
    
    //中序遍历
    public int midOrder(TreeNode root,int[] arr,int index){
        //递归出口
        if(root == null){
            return index;
        }
        
        int temp = midOrder(root.left,arr,index);//递归左子树
        arr[temp] = root.val;//遍历根节点
        temp++;//数组下标索引加1
        temp = midOrder(root.right,arr,temp);//递归右子树
        return temp;//返回数组下标索引
    }
    
    //后序遍历
    public int afterOrder(TreeNode root,int[] arr,int index){
        //递归出口
        if(root == null){
            return index;
        }
        
        int temp = afterOrder(root.left,arr,index);//递归左子树
        temp = afterOrder(root.right,arr,temp);//递归右子树
        arr[temp] = root.val;//遍历根节点
        temp++;//数组下标索引加1
        return temp;//返回数组下标索引
    }
}