前序遍历（Pre Order Traversal）算法：基准条件及双方法实现问询

我来帮你理清这个问题——其实你之前绕了弯路，前序遍历的迭代实现和终止条件远没有你想的复杂！

先明确核心的基准条件 #

你不需要纠结那些复杂的父节点、多层右节点判断，最关键的基准条件其实非常简单：当输入的根节点为null时，直接返回空的ArrayList。这是所有树遍历算法的基础边界情况，也是第一个方法的核心职责。

两个方法的分工设计 #

我给你梳理下清晰的职责划分，完全匹配你想要的双方法思路：

1. 入口方法（对外暴露）

   • 负责初始化存储结果的ArrayList
   • 检查基准条件：如果根节点为空，直接返回空列表
   • 如果根节点有效，调用第二个迭代方法来填充结果列表

2. 迭代遍历方法（核心实现）

   • 用**栈（Stack）**模拟递归过程（前序遍历的逻辑是「根→左→右」，栈的后进先出特性刚好能完美适配这个顺序）
   • 迭代的终止条件极其可靠：当栈为空时，停止迭代——栈里存的是待处理的节点，栈空就意味着所有节点都已经被访问并加入列表了，完全不需要计数器或追踪父节点这种复杂操作

具体代码示例（以Java为例） #

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PreorderTraversal {
    // 第一个方法：入口，处理基准条件
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        // 基准条件：根节点为空，直接返回空列表
        if (root == null) {
            return result;
        }
        // 调用迭代方法填充结果
        iterativePreorder(root, result);
        return result;
    }

    // 第二个方法：核心迭代逻辑
    private void iterativePreorder(TreeNode node, List<Integer> result) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);

        // 迭代终止条件：栈为空
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            // 前序遍历：先访问根节点，加入列表
            result.add(current.val);

            // 注意：栈是后进先出，所以先压右节点，再压左节点
            // 这样弹出的时候会先处理左节点，符合「根→左→右」的顺序
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }

    // 树节点定义（供参考）
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }
}

为什么你之前的思路会出问题？ #

• 「判断无法获取右节点且无法获取父节点的右节点」：这种逻辑太依赖树的层级和父节点追踪，不仅实现复杂，而且在多层树、不平衡树中极易出错，完全没必要
• 「用计数器和节点总数对比」：首先你需要额外遍历一次树来获取节点总数，增加了时间复杂度；其次如果树在遍历过程中被修改（哪怕你的场景不会，逻辑上也有漏洞），计数器就会失效；最关键的是，栈为空的条件已经天然能判断遍历完成，完全不需要多此一举

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