学习纪录：js算法（五十一）：统计二叉树中好节点的数量
统计二叉树中好节点的数量给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数量。
「好节点」X 界说为：从根到该节点 X 所颠末的节点中，没有任何节点的值大于 X 的值。
图一：
https://i-blog.csdnimg.cn/direct/26fd8e081ab94c8a94018f6eae88ce0e.png#pic_center
图二：
https://i-blog.csdnimg.cn/direct/24ec92eb0c0d421998a5d7a362770189.png#pic_center
示例 1：如图一
输入：root =
输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。
示例 2：如图二
输入：root =
输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
示例 3：
输入：root =
输出：1
解释：根节点是好节点。
我的思路
不会。。。
网上思路
递归
网上思路
var goodNodes = function(root) {
let count = 0;
function dfs(node, maxVal) {
if (node === null) return;
if (node.val >= maxVal) {
count++;
}
maxVal = Math.max(maxVal, node.val);
dfs(node.left, maxVal);
dfs(node.right, maxVal);
}
dfs(root, -Infinity);
return count;
};
解说
要计算二叉树中好节点的数量，我们可以使用深度优先搜索（DFS）的方法，递归地遍历树中的每个节点。在遍历过程中，我们必要维护一个从根节点到当前节点的路径上的最大值。如果当前节点的值大于等于这个最大值，那么它就是一个好节点。接下来，我们更新最大值为当前节点的值，然后递归地遍历左右子树。
[*]初始化：界说一个计数器 count 用于纪录好节点的数量，以及一个最大值 maxVal 用于存储从根到当前节点路径上的最大值。
[*]递归函数：界说一个递归函数 dfs(node, maxVal)，它接收当前节点和最大值作为参数。
[*]基本环境：如果当前节点 node 为空，直接返回。
[*]更新计数器：如果当前节点的值大于等于 maxVal，则增加 count 计数器，表现找到了一个好节点。
[*]更新最大值：更新 maxVal 为当前节点的值和 maxVal 中的较大者。
[*]递归调用：递归地遍历左右子树，将更新后的 maxVal 传入。
[*]返回结果：在主函数中，调用 dfs(root, -Infinity) 开始遍历，并返回 count。
总结
国庆节快乐！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]