Java二叉树根到叶最小路径求解Bug修复与算法优化

• 回溯操作不对称导致路径栈污染：原代码仅在递归左右子节点前才将当前节点加入路径，叶子节点单独执行加入操作后直接return，未对应移除叶子节点，每访问一个叶子节点就会在路径栈中多残留一个元素，后续递归右子树时会重复添加根节点值。
• 剪枝逻辑错误：原剪枝条件currentSum > minsum[0]仅在所有节点值非负时生效，若存在负数值节点，当前和大于最小值时后续加负数仍可能得到更小和，会漏过正确解。
• 时间复杂度判断正确：该问题必须遍历所有节点才能确认全局最小路径，回溯法每个节点仅访问1次，时间复杂度为O(N)，不存在渐近时间复杂度更优的解法。

将路径添加/移除的逻辑改为对称结构：进入当前节点时统一加入路径、累加和，处理完当前节点（叶子判断+左右子树递归）后统一回溯移除，从根源上避免漏删导致的栈污染；移除错误的剪枝逻辑。
修复后的核心回溯代码如下：

private static void backtrack(TreeNode node, List<Integer> result, List<Integer> currentpath, int currentSum, int[] minsum) {
    if (node == null) {
        return;
    }
    // 进入节点时统一做选择：加入当前路径、累加和
    currentpath.add(node.val);
    currentSum += node.val;

    // 判断是否为叶子节点
    if (node.left == null && node.right == null) {
        if (currentSum < minsum[0]) {
            minsum[0] = currentSum;
            result.clear();
            result.addAll(new ArrayList<>(currentpath));
        }
    } else {
        // 递归左右子树
        backtrack(node.left, result, currentpath, currentSum, minsum);
        backtrack(node.right, result, currentpath, currentSum, minsum);
    }

    // 离开节点时统一撤销选择：移除当前路径最后一个元素
    currentpath.remove(currentpath.size() - 1);
}

针对给出的测试用例，正确最小路径为[-1, 1, 0, 0]，最小和为0，修复后代码可正确输出该结果，不会出现根节点重复的问题。

补充说明：若题目明确所有节点值为非负，可以增加剪枝逻辑，判断currentSum >= minsum[0]时直接返回，能减少部分递归调用，但不会改变最坏情况下O(N)的时间复杂度。

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