题解 | #二叉树的前序遍历#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        //方法一：递归遍历
        //特殊值处理，当树为空时，直接返回空数组
//        if(root == null){
//            return null;
//        }
//        //创建一个ArrayList对象，因为书的节点个数未知
//        ArrayList<Integer> arrayList = new ArrayList<>();
//        //先根遍历
//        prepRoot(root,arrayList);
//        final Object[] obj = arrayList.toArray();  //将ArrayList对象转换为Object数组
//        int length = obj.length;  //获取Object数组的长度
//        int[] arr = new int[length];  //新创建一个长度为Object数组的长度的整型数组
//        for(int i=0;i<length;i++){
//            arr[i] = (int) obj[i];  //遍历数组，将Object对象转换为整型数
//        }
//        return arr;

        //方法二：迭代遍历
        //特殊值处理，当树为空时，直接返回空数组
        if(root == null){
            return new int[0];
        }
        //创建一个ArrayList对象，因为书的节点个数未知
        ArrayList<Integer> arrayList = new ArrayList<>();
        //创建一个栈，存储的对象是树的节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);  //将根节点压入栈
        while (!stack.isEmpty()){  //当栈不为空时，退出循环
            final TreeNode pop = stack.pop();  //弹出栈顶元素
            arrayList.add(pop.val);  //遍历栈顶元素，并将栈顶元素添加到ArrayList数组
            if(pop.right != null){  //如果栈顶元素右节点不为空，压入栈中
                stack.push(pop.right);
            }
            if(pop.left != null){  //如果栈顶元素左节点不为空，压入栈中
                stack.push(pop.left);
            }
        }
        final Object[] obj = arrayList.toArray();  //将ArrayList对象转换为Object数组
        int length = obj.length;  //获取Object数组的长度
        int[] arr = new int[length];  //新创建一个长度为Object数组的长度的整型数组
        for(int i=0;i<length;i++){
            arr[i] = (int) obj[i];  //遍历数组，将Object对象转换为整型数
        }
        return arr;
    }
    
    /**
     * 题目描述：先根遍历，
     * @param root  树的根节点
     * @param arrayList 数组，保存树节点的值
     */
    public static void prepRoot(TreeNode root,ArrayList<Integer> arrayList){
        if(root == null){//如果根节点为空，则直接返回
            return ;
        }
        arrayList.add(root.val); //先遍历根节点
        prepRoot(root.left,arrayList);  //再遍历左子树
        prepRoot(root.right,arrayList);  //后遍历右子树
    }
}