Java初学者求助：无参二叉树前序遍历转ArrayList实现问题

嘿，作为Java初学者，能尝试自己实现遍历逻辑已经很棒啦！不过你的代码确实存在几个关键问题，我来帮你拆解并给出正确的实现～

先说说你现有代码的问题 #

• list.set()的致命错误：刚创建的ArrayList是空的（初始大小为0），直接调用set(index, value)会抛出IndexOutOfBoundsException——因为这个索引位置根本不存在元素。你应该用list.add()来向列表中追加元素。
• 遍历逻辑完全不符合前序规则：你的循环只是反复访问根节点的左/右节点，没有真正深入子树。比如第一个while循环会无限执行（因为root始终指向根节点，它的左节点不会凭空消失），而且就算能退出，也只是重复添加根节点左孩子的值，完全没遍历左子树的其他节点；右子树的处理也犯了同样的错误。
• 没理解前序遍历的核心：前序遍历的顺序是根节点 → 左子树前序遍历 → 右子树前序遍历，这是一个递归的过程，要么用递归实现，要么用栈模拟递归的调用过程。

正确的实现方式 #

方式1：递归实现（最易理解，适合初学者） #

我们可以写一个辅助递归方法，让它负责遍历节点并把值加入列表，主方法只需要初始化列表并触发递归：

public ArrayList<T> toPreOrderList() {
    ArrayList<T> list = new ArrayList<>();
    // 调用辅助方法开始遍历
    preOrderHelper(root, list);
    return list;
}

// 私有辅助方法，负责递归遍历节点
private void preOrderHelper(Node<T> currentNode, ArrayList<T> resultList) {
    // 递归终止条件：遇到空节点直接返回
    if (currentNode == null) {
        return;
    }
    // 1. 先添加当前节点的值（前序的"根"）
    resultList.add(currentNode.getData());
    // 2. 递归遍历左子树（前序的"左"）
    preOrderHelper(currentNode.getLeft(), resultList);
    // 3. 递归遍历右子树（前序的"右"）
    preOrderHelper(currentNode.getRight(), resultList);
}

方式2：迭代实现（用栈模拟递归，适合理解底层逻辑） #

如果不想用递归，可以用栈来手动管理遍历的节点，模拟递归的调用栈过程：

import java.util.Stack;

public ArrayList<T> toPreOrderList() {
    ArrayList<T> list = new ArrayList<>();
    // 空树直接返回空列表
    if (root == null) {
        return list;
    }
    
    Stack<Node<T>> nodeStack = new Stack<>();
    nodeStack.push(root);
    
    while (!nodeStack.isEmpty()) {
        Node<T> current = nodeStack.pop();
        // 先处理当前节点（根）
        list.add(current.getData());
        
        // 注意：栈是后进先出，所以先压右子节点，再压左子节点
        // 这样弹出的时候会先处理左子节点，符合前序"根→左→右"的顺序
        if (current.getRight() != null) {
            nodeStack.push(current.getRight());
        }
        if (current.getLeft() != null) {
            nodeStack.push(current.getLeft());
        }
    }
    return list;
}

几个关键提醒 #

• 永远不要忽略空节点的处理，否则很容易抛出NullPointerException
• 向空的ArrayList添加元素一定要用add()，set()只能修改已存在索引位置的元素
• 前序遍历的核心顺序是根→左→右，不管用哪种实现方式，都要严格遵循这个顺序

内容的提问来源于stack exchange，提问作者SpaceToon