树与图简单2 种解法

#144二叉树的前序遍历

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

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

解题主线

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

解法 1：递归前序遍历

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

时间复杂度

O(n)

空间复杂度

O(h)

144. 二叉树的前序遍历 · 递归前序遍历

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) 最坏

144. 二叉树的前序遍历 · 迭代前序遍历

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.javaleetcode/src/main/java/tree/Q94_144_145_traversal.java