LeetCode Java常用：如何用递归实现二叉树的前序遍历？

Question

在LeetCode中使用Java实现二叉树前序遍历的递归方法时，常见的技术问题是如何正确地定义递归终止条件以及确保节点访问顺序符合前序规则（根-左-右）。如果终止条件设置不当，可能会导致栈溢出或结果错误。例如，在递归函数中忘记检查节点是否为空（`if (node == null) return;`），会导致程序尝试访问空指针而崩溃。此外，部分初学者可能对递归调用的顺序存在疑惑，从而打乱了“先处理根节点，再依次递归左子树和右子树”的逻辑。这会改变遍历顺序，导致输出不符合前序要求。因此，清晰地定义递归结构并严格遵循前序遍历规则是解决问题的关键。

Answer 1

1. 常见技术问题分析

在LeetCode中使用Java实现二叉树前序遍历时，初学者常遇到两个主要问题：递归终止条件的定义和节点访问顺序的正确性。

• 递归终止条件：如果未检查节点是否为空（`if (node == null) return;`），程序可能尝试访问空指针导致崩溃。
• 节点访问顺序：部分开发者对递归调用的顺序存在疑惑，可能会打乱“根-左-右”的逻辑，从而改变遍历顺序。

2. 解决方案与代码示例

为了解决上述问题，我们需要明确递归终止条件并严格遵循前序遍历规则。以下是一个完整的Java代码示例：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return; // 递归终止条件
        result.add(node.val); // 访问根节点
        preorderHelper(node.left, result); // 递归左子树
        preorderHelper(node.right, result); // 递归右子树
    }
}
    

3. 分析过程

通过逐步分析，我们可以更清晰地理解如何避免常见错误：

1. 首先，确保每次递归调用时检查节点是否为空。这是防止栈溢出或空指针异常的关键。
2. 其次，按照“根-左-右”的顺序依次处理每个节点。任何顺序的改变都会导致结果不符合前序遍历的要求。

以下是前序遍历的逻辑流程图：

graph TD;
            A[开始] --> B[检查节点是否为空];
            B --是--> C[返回];
            B --否--> D[访问当前节点];
            D --> E[递归左子树];
            E --> F[递归右子树];
            F --> G[结束];

4. 深入探讨

对于有经验的开发者，还可以考虑以下优化点：

优化方向	具体实现
减少递归深度	通过迭代方法代替递归，利用显式栈结构存储待访问节点。
提高可读性	将递归逻辑封装到独立的方法中，使主函数更加简洁。

尽管迭代方法可以避免递归带来的栈溢出风险，但对于初学者来说，递归方法更直观且易于理解。