题解 | 二叉树的前序遍历

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 {
    /**
     * 
     */
    public int[] preorderTraversal (TreeNode root) {
        // 1. 创建一个 List 用来动态存放遍历到的节点值
        ArrayList<Integer> list = new ArrayList<>();

        // 2. 调用递归辅助函数，把 list 传进去收集数据
        traverse(root, list);

        // 3. 将 ArrayList<Integer> 转换为题目要求的 int[] 数组
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }

    // 真正的递归遍历
    public void traverse(TreeNode root, ArrayList<Integer> list) {
        // 出口：如果节点为空，直接返回
        if (root == null) return;

        // 前序遍历的核心
        list.add(root.val);  // 1. 先访问根节点
        traverse(root.left, list);  // 2. 再递归遍历左子树
        traverse(root.right, list);  // 3. 最后递归遍历右子树
    }
}