二叉树好节点计数：现有递归解法的错误修正咨询

给定二叉树的根节点root，若从根到节点X的路径中不存在值大于X的节点，则称X为好节点，需要返回二叉树中好节点的总数。

现有代码在部分测试用例中运行正确，但在测试用例[2,null,4,10,8,null,null,4]中得到错误结果3（正确结果应为4）。

问题根源 #

原代码使用了静态全局变量max和count来跟踪路径最大值和计数：

• 当递归遍历到节点10时，全局max被更新为10；
• 回溯到节点4后遍历右子树节点8时，全局max仍保持为10，导致节点8被错误判定为非好节点（实际路径2->4->8的最大值是4，8>=4，属于好节点）。
  全局变量的状态在递归的不同分支间共享，无法在回溯时自动恢复上一层的路径最大值，导致计数错误。

修正方案 #

去掉全局变量，改用递归参数传递当前路径的最大值，让每个递归分支维护独立的路径状态，回溯时自动恢复上一层的最大值。

修正后的代码：

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;
    }
}

class Solution {
    public int goodNodes(TreeNode root) {
        // 初始调用，路径最大值为根节点的值（根节点必然是好节点）
        return countGoodNodes(root, root.val);
    }
    
    private int countGoodNodes(TreeNode node, int currentMax) {
        if (node == null) {
            return 0;
        }
        
        int currentCount = 0;
        // 判断当前节点是否为好节点
        if (node.val >= currentMax) {
            currentCount = 1;
            // 更新路径最大值为当前节点的值，供子节点使用
            currentMax = node.val;
        }
        
        // 递归累加左、右子树的好节点数量
        currentCount += countGoodNodes(node.left, currentMax);
        currentCount += countGoodNodes(node.right, currentMax);
        
        return currentCount;
    }
}

关键改动说明 #

1. 移除全局变量：不再使用静态max和count，避免分支间的状态污染。
2. 递归参数传递路径最大值：每个递归调用携带当前路径的最大值，确保左、右子树的遍历互不干扰。
3. 局部计数累加：每个递归函数返回当前子树的好节点数量，通过递归调用的返回值累加得到总数，逻辑更清晰。

测试验证 #

对于测试用例[2,null,4,10,8,null,null,4]：

• 根节点2：计数1，路径最大值2；
• 节点4：计数1（累计2），路径最大值4；
• 节点10：计数1（累计3），路径最大值10；
• 节点8：计数1（累计4），路径最大值8；
• 节点4（8的子节点）：非好节点，计数0；
  最终返回4，符合正确结果。

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