树与图简单2 种解法

#144二叉树的前序遍历

按根节点、左子树、右子树的顺序返回节点值。

#二叉树#深度优先搜索#栈

原题

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

查看原题

解题主线

迭代时先压右孩子再压左孩子，才能让左孩子先出栈。

解法 1：递归前序遍历

访问根后依次递归左右子树。

时间复杂度： O(n)
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 访问顺序始终保持“根节点、左子树、右子树”的前序语义。
        // 空节点不产生结果，每个非空节点只会递归访问或入栈一次。
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    private void preorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}

解法 2：迭代前序遍历

栈弹出即访问，并按右后左的顺序压栈。

时间复杂度： O(n)
空间复杂度： O(h) 平均，O(n) 最坏

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 访问顺序始终保持“根节点、左子树、右子树”的前序语义。
        // 空节点不产生结果，每个非空节点只会递归访问或入栈一次。
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

边界与易错点

递归结果应在每次入口创建，避免实例字段在重复调用时累积。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q144_tree_preorder.java
leetcode/src/main/java/tree/Q94_144_145_traversal.java