专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

马上就要到五一了，今年的五一也是连休5天，很多人想利用这个时间回趟老家或者出去游玩，所以这段时间也是买票流量的高峰期。据12306显示今天只能购买到4月30号的票，5月1号的票暂时还不能购买。

结果今天早上一条12306崩了的消息登上了热搜，有不少网友反应今天早上买票的时候出现故障，网友也是非常愤怒，希望换程序员。实际上12306崩过也不是这一回了，没办法，流量太大，尤其是春节以及五一，十一这种长假，流量都会集中爆发。我刚试了下，没有出现奔溃的现象，应该是修复了，有需要的现在可以购买了。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1448题：统计二叉树中好节点的数目，难度是中等。

给你一棵根为 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" 比它大。

  • 二叉树中节点数目范围是 [1, 10^5] 。

  • 每个节点权值的范围是 [-10^4, 10^4] 。

问题分析

这题让计算二叉树中好节点的个数，所谓好节点就是从根节点开始到当前节点这条路径上没有比当前节点值大的节点，那么当前节点就是好节点。

我们直接使用dfs对二叉树进行遍历，需要记录从根节点到当前节点这条路径上的最大值。如果当前节点大于等于这个最大值，说明这条路径上没有比当前节点值大的节点，所以当前节点就是好节点，最后累加好节点的个数即可。

JAVA：

public int goodNodes(TreeNode root) {     return dfs(root, Integer.MIN_VALUE); } private int dfs(TreeNode root, int maxV) {     if (root == null)         return 0;     int left = dfs(root.left, Math.max(root.val, maxV));     int right = dfs(root.right, Math.max(root.val, maxV));     return left + right + (root.val < maxV ? 0 : 1); }

C++：

public:     int goodNodes(TreeNode *root) {         return dfs(root, INT_MIN);     }     int dfs(TreeNode *root, int maxV) {         if (root == nullptr)             return 0;         int left = dfs(root->left, max(root->val, maxV));         int right = dfs(root->right, max(root->val, maxV));         return left + right + (root->val < maxV ? 0 : 1);     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。