欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

学习记录:JS 算法 (51):计算二叉树中好节点的数量

最编程 2024-10-02 21:20:33
...

文章目录

    • 统计二叉树中好节点的数目
      • 网上思路
    • 总结

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

给你一棵根为 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
解释:根节点是好节点。

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

网上思路

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)的方法,递归地遍历树中的每个节点。在遍历过程中,我们需要维护一个从根节点到当前节点的路径上的最大值。如果当前节点的值大于等于这个最大值,那么它就是一个好节点。接下来,我们更新最大值为当前节点的值,然后递归地遍历左右子树。

  1. 初始化:定义一个计数器 count 用于记录好节点的数量,以及一个最大值 maxVal 用于存储从根到当前节点路径上的最大值。
  2. 递归函数:定义一个递归函数 dfs(node, maxVal),它接收当前节点和最大值作为参数。
  3. 基本情况:如果当前节点 node 为空,直接返回。
  4. 更新计数器:如果当前节点的值大于等于 maxVal,则增加 count 计数器,表示找到了一个好节点。
  5. 更新最大值:更新 maxVal 为当前节点的值和 maxVal 中的较大者。
  6. 递归调用:递归地遍历左右子树,将更新后的 maxVal 传入。
  7. 返回结果:在主函数中,调用 dfs(root, -Infinity) 开始遍历,并返回 count

总结

国庆节快乐!

推荐阅读