Medium

题目描述

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的路径中，没有任何节点的值大于 X 的值。

示例 1：

输入：root = [3,1,4,3,null,1,5]
输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是一个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。

示例 2：

输入：root = [3,3,null,4,2]
输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。

示例 3：

输入：root = [1]
输出：1
解释：根节点是好节点。

提示：

  • 二叉树中节点数目范围是 [1, 10^5] 。
  • 每个节点权值的范围是 [-10^4, 10^4] 。

解题思路

解题思路

这道题目的核心是理解"好节点"的定义：从根节点到当前节点的路径上，没有任何节点的值大于当前节点的值。

深度优先搜索（DFS）解法（推荐）

我们可以使用深度优先搜索来遍历二叉树，在遍历过程中维护从根节点到当前节点路径上的最大值。对于每个节点，我们检查它是否大于等于路径上的最大值：

  • 如果是，则该节点是好节点，计数器加1，并更新路径最大值
  • 如果不是，则该节点不是好节点，但仍需继续遍历其子树

具体步骤：

  1. 从根节点开始，初始最大值为根节点的值
  2. 对于当前节点，如果其值大于等于路径最大值，则为好节点
  3. 递归遍历左右子树，传递更新后的路径最大值
  4. 返回所有好节点的总数

这种方法时间复杂度为O(n)，空间复杂度为O(h)，其中h为树的高度。

广度优先搜索（BFS）解法

也可以使用BFS，在队列中同时存储节点和对应的路径最大值，但DFS更加直观和高效。

代码实现

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, root->val);
    }
    
private:
    int dfs(TreeNode* node, int maxVal) {
        if (!node) return 0;
        
        int count = 0;
        if (node->val >= maxVal) {
            count = 1;
            maxVal = node->val;
        }
        
        count += dfs(node->left, maxVal);
        count += dfs(node->right, maxVal);
        
        return count;
    }
};

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_val):
            if not node:
                return 0
            
            count = 0
            if node.val >= max_val:
                count = 1
                max_val = node.val
            
            count += dfs(node.left, max_val)
            count += dfs(node.right, max_val)
            
            return count
        
        return dfs(root, root.val)

public class Solution {
    public int GoodNodes(TreeNode root) {
        return Dfs(root, root.val);
    }
    
    private int Dfs(TreeNode node, int maxVal) {
        if (node == null) return 0;
        
        int count = 0;
        if (node.val >= maxVal) {
            count = 1;
            maxVal = node.val;
        }
        
        count += Dfs(node.left, maxVal);
        count += Dfs(node.right, maxVal);
        
        return count;
    }
}

var goodNodes = function(root) {
    const dfs = (node, maxVal) => {
        if (!node) return 0;
        
        let count = 0;
        if (node.val >= maxVal) {
            count = 1;
            maxVal = node.val;
        }
        
        count += dfs(node.left, maxVal);
        count += dfs(node.right, maxVal);
        
        return count;
    };
    
    return dfs(root, root.val);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历二叉树的每个节点一次，n为节点总数
空间复杂度O(h)递归调用栈的深度，h为树的高度，最坏情况下为O(n)