1448. Count Good Nodes in Binary Tree

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number}
 */

题目给我们一个二叉树的根节点

要求我们计算出有多少个节点是根节点到当前节点的最大元素

最后返回节点数量

解题思路

要判断从根节点到叶子节点的路径，一般选择 DFS

在 DFS 过程中，我们在参数保存当前路径上的最大节点的值 largest，通过当前节点的值域 largest 的比较我们就能判断当前节点是否是路径上的最大元素

如果是的话，我们可以把返回的节点数量 +1 并且更新 largest

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    let res = 0

    const dfs = (node, largest) => {
        if(!node) {
            return
        }
        if(node.val >= largest) {
            res++
            largest = node.val
        }

        dfs(node.left, largest)
        dfs(node.right, largest)
    }

    dfs(root, Number.MIN_SAFE_INTEGER)

    return res
};

复杂度分析

时间

需要遍历所有的树节点，所以是 O(n)，n 代表树的所有节点数量

空间

Dfs 迭代取决于树的高度，最差的情况是 O(n)，最好的情况是 O(log n)