[!info] related notes 算法面试题型 MOC 二叉树高频题

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

题目

1448. 统计二叉树中好节点的数目 - 力扣（LeetCode）

从根到当前节点的路径上，没有比当前值更大的节点时，该节点是好节点；相等也符合。根节点总符合。传入的 max 是当前路径的最大值，不能用横跨兄弟子树的全局最大值。

题解

链表-二叉树-回溯

var goodNodes = function(root) {
    let res = 0;
    if (!root) return 0;
    // 把 当前路线上的最大值传下去
    function dfs(node, max) {
        if (!node) return;
        if (node.val >= max) {
            res++;
        }
        max = Math.max(max, node.val);
        dfs(node.left,max);
        dfs(node.right,max)
    }
    dfs(root, -Infinity)
    return res;
};

时间 O(n)，递归栈 O(h)。传参使左右分支各自继承路径状态，处理完左子树不应污染右子树。