学习纪录：js算法（五十一）：统计二叉树中好节点的数量 ...

统计二叉树中好节点的数量

   给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数量。
「好节点」X 界说为：从根到该节点 X 所颠末的节点中，没有任何节点的值大于 X 的值。
  图一：

图二：

1. 示例 1：如图一
2. 输入：root = [3,1,4,3,null,1,5]
3. 输出：4
4. 解释：图中蓝色节点为好节点。
5. 根节点 (3) 永远是个好节点。
6. 节点 4 -> (3,4) 是路径中的最大值。
7. 节点 5 -> (3,4,5) 是路径中的最大值。
8. 节点 3 -> (3,1,3) 是路径中的最大值。
10. 示例 2：如图二
11. 输入：root = [3,3,null,4,2]
12. 输出：3
13. 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
15. 示例 3：
16. 输入：root = [1]
17. 输出：1
18. 解释：根节点是好节点。

复制代码

  我的思路
不会。。。
网上思路
递归
  网上思路

1. var goodNodes = function(root) {
2.     let count = 0;
4.     function dfs(node, maxVal) {
5.         if (node === null) return;
6.         
7.         if (node.val >= maxVal) {
8.             count++;
9.         }
10.         
11.         maxVal = Math.max(maxVal, node.val);
12.         
13.         dfs(node.left, maxVal);
14.         dfs(node.right, maxVal);
15.     }
16.    
17.     dfs(root, -Infinity);
18.     return count;
19. };

复制代码

  解说
要计算二叉树中好节点的数量，我们可以使用深度优先搜索（DFS）的方法，递归地遍历树中的每个节点。在遍历过程中，我们必要维护一个从根节点到当前节点的路径上的最大值。如果当前节点的值大于等于这个最大值，那么它就是一个好节点。接下来，我们更新最大值为当前节点的值，然后递归地遍历左右子树。
  

• 初始化：界说一个计数器 count 用于纪录好节点的数量，以及一个最大值 maxVal 用于存储从根到当前节点路径上的最大值。
  
• 递归函数：界说一个递归函数 dfs(node, maxVal)，它接收当前节点和最大值作为参数。
  
• 基本环境：如果当前节点 node 为空，直接返回。
  
• 更新计数器：如果当前节点的值大于等于 maxVal，则增加 count 计数器，表现找到了一个好节点。
  
• 更新最大值：更新 maxVal 为当前节点的值和 maxVal 中的较大者。
  
• 递归调用：递归地遍历左右子树，将更新后的 maxVal 传入。
  
• 返回结果：在主函数中，调用 dfs(root, -Infinity) 开始遍历，并返回 count。
  

  总结

国庆节快乐！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。