题目大意：
统计二叉树中好节点的数目
给你一棵根为 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]。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1448
解题思路分析：
这是一道典型使用dfs解决二叉树问题的题目。利用dfs深度优先搜索来递归遍历二叉树的每一个节点，并且在递归函数的参数中传入当前路径中的最大值max。如果当前节点大于等于max，说明当前节点属于一个好节点，当前递归的返回结果为1，同时更新max为当前节点。然后dfs递归至其左右两个子节点，并将递归结果累加至当前递归的返回结果。
实现代码：
public int goodNodes(TreeNode root) {
return dfs(root,root.val); // dfs求解
}
// root：当前节点
// max：当前路径中最大值
int dfs(TreeNode root, int max){
int res=0; // 返回结果
if(root.val>=max){ // 如果当前节点大于等于max
res=1; // 当前节点是一个好节点
max=root.val; // 更新max值
}
if(root.left!=null){ // dfs递归至左子节点
res+=dfs(root.left,max);
}
if(root.right!=null){ // dfs递归至右子节点
res+=dfs(root.right,max);
}
return res;
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 69.99% of Java online submissions for Count Good Nodes in Binary Tree.
Memory Usage: 55 MB, less than 100.00% of Java online submissions for Count Good Nodes in Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1448-count-good-nodes-in-binary-tree-解题思路分析/