Leetcode：计算二叉树中的好节点

Question

给定一个二叉树根，如果从根到 X 的路径中不存在值大于 X 的节点，则树中的节点 X 被命名为良好。

返回二叉树中好节点的数量。

这是我的解决方案：

/**
 * Definition for a binary tree node.
 * 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) {

        int ans = dfs(root);
        return ans;
        }

        int maxL = 0;
        int maxR = 0;
        int countL =0;
        int countR = 0;
        private int dfs(TreeNode root) {
           
            if(root == null) {
                return 0;
            }
           int valL = dfs(root.left);
          if(valL> root.val) {
            countL++;
          }
          else{
            if(root.val>maxL) {
                countL = 0;
                maxL = root.val;
            }
            else{
             countL = countL;
            }
          }
    
           int valR = dfs(root.right);
           if(valR>root.val) {
            countR++;

           }
           else{
            if(root.val>maxR) {
                countR = 0;
                maxR = root.val;
            }
            else{
                countL = countL;
            }
           }
          
          return countR + countL;
        }
       
    }

我为其编写的解决方案在逻辑上对我来说似乎是正确的。它为我提供了所有测试用例的输出 0。我不知道为什么。是因为我将其外部的四个变量初始化为 0，并且这就是从 GoodNodes 方法调用时它所保留的值吗？如果有人能指出我的逻辑中的确切错误，我将非常感激。每当遇到 maxL 或 maxR 小于它的节点时，我将计数设置为 0，因为这意味着如果当前节点的值超过了最大节点本身，则当前节点之前的所有节点都不能算作好节点.

Answer 1

有几个问题：

• 虽然

  dfs

  返回一个 count，但您可以将该计数与 node value 进行比较，在表达式

  valL> root.val

  中：这是在比较彼此无关的事物。

• maxL

  永远不会减少，只会增加，但如果您所在的路径与找到最大值的路径不同，则它应该不再相关。为此，请使用本地参数，而不是使用字段，这样当您从递归返回时，此最大值就会回到进行递归调用之前的值。

更正的方法是不使用实例变量来实现此目的，而是使用一个额外的参数

dfs

来表示到当前节点的路径上的最大值。该函数应返回递归调用的计数总和，如果当前节点也是好节点，则加 1：

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }

    private int dfs(TreeNode root, int maxOnPath) {
        if (root == null) {
            return 0;
        }
        int count = root.val <= maxOnPath ? 1 : 0;
        maxOnPath = Math.max(root.val, maxOnPath);
        return count + dfs(root.left, maxOnPath) + dfs(root.right, maxOnPath);
    }    
}