本文共 4202 字，大约阅读时间需要 14 分钟。

二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。

示例：

输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]

思路+代码+注释：

public List preorderTraversal(TreeNode root) { List res=new ArrayList preorderTraversal(root,res); return res; }

private void preorderTraversal(TreeNode node,List res) { if (node==null) { return; } res.add(node.val); preorderTraversal(node.left,res); preorderTraversal(node.right,res); }

代码解释：

前序遍历的思路是根→左→右。我们采用递归的方式来处理树的节点。当节点为null时，直接返回；当节点不为null时，将节点的值添加到res中，然后递归处理左子节点，最后递归处理右子节点。

示例分析：

输入的二叉树结构如下： 1 /

前序遍历的结果是：1→2→3

代码实现：

使用递归的方式，先处理当前节点的值，然后递归处理左子节点，最后递归处理右子节点。

代码注释：

public List preorderTraversal(TreeNode root) { List res=new ArrayList preorderTraversal(root,res); return res; }

private void preorderTraversal(TreeNode node,List res) { if (node==null) { return; } res.add(node.val); preorderTraversal(node.left,res); preorderTraversal(node.right,res); }

代码解释：

示例输出：

输入: [1,null,2,3] 输出: [1,2,3]

代码实现的核心思想是利用递归来实现前序遍历的顺序，即先处理根节点，再处理左子节点，最后处理右子节点。

代码优化：

为了提高代码的可读性和性能，可以优化代码如下：

public List preorderTraversal(TreeNode root) { List res=new ArrayList if (root != null) { res.add(root.val); preorderTraversal(root.left, res); preorderTraversal(root.right, res); } return res; }

private void preorderTraversal(TreeNode node,List res) { if (node == null) { return; } res.add(node.val); preorderTraversal(node.left, res); preorderTraversal(node.right, res); }

这一优化可以减少一些无用的检查，使代码更加简洁。

代码注释优化：

为了让代码更易理解，可以添加更详细的注释：

public List preorderTraversal(TreeNode root) { /* * 返回二叉树的前序遍历结果 * @param root 二叉树的根节点 * @return 前序遍历结果的列表 / List res=new ArrayList / * 如果根节点不为空，将其值添加到结果列表中 * 然后递归处理左子节点，最后递归处理右子节点 */ if (root != null) { res.add(root.val); preorderTraversal(root.left, res); preorderTraversal(root.right, res); } return res; }

private void preorderTraversal(TreeNode node,List res) { /* * 如果当前节点为空，直接返回 / if (node == null) { return; } / * 将当前节点的值添加到结果列表中 / res.add(node.val); / * 递归处理左子节点 / preorderTraversal(node.left, res); / * 递归处理右子节点 */ preorderTraversal(node.right, res); }

代码优化后的注释更加详细，方便开发者理解。

示例测试：

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

代码运行结果：

调用 preorderTraversal(1, res) → res.add(1) 调用 preorderTraversal(null, res) → 返回 调用 preorderTraversal(2, res) → res.add(2) 调用 preorderTraversal(null, res) → 返回 调用 preorderTraversal(3, res) → res.add(3) 调用 preorderTraversal(null, res) → 返回

最终 res = [1,2,3]

代码性能：

该算法的时间复杂度为 O(n)，其中 n 是二叉树的节点数。空间复杂度为 O(h)，h 是二叉树的高度。

代码适用范围：

该算法适用于所有二叉树的前序遍历问题，包括二叉树的子树前序遍历、偶数层序遍历等。

代码扩展：

如果需要对二叉树的其他遍历方式进行实现，可以参考以下代码：

• 中序遍历： public List inorderTraversal(TreeNode root) { List res=new ArrayList inorderTraversal(root, res); return res; }

  private void inorderTraversal(TreeNode node,List res) { if (node == null) { return; } inorderTraversal(node.left, res); res.add(node.val); inorderTraversal(node.right, res); }

• 后序遍历： public List postorderTraversal(TreeNode root) { List res=new ArrayList postorderTraversal(root, res); return res; }

  private void postorderTraversal(TreeNode node,List res) { if (node == null) { return; } postorderTraversal(node.left, res); postorderTraversal(node.right, res); res.add(node.val); }

通过这种方式，可以轻松扩展对不同遍历方式的实现。

代码总结：

前序遍历是处理根节点，然后处理左子节点，最后处理右子节点。通过递归的方式，可以实现二叉树的前序遍历。

代码优化建议：

为了提高代码性能，可以使用循环实现前序遍历，而不是递归。递归在处理非常深的二叉树时，可能会导致栈溢出问题。

代码实战：

在实际开发中，可以将二叉树的节点用 JavaBean 标签表示，如：