LeetCode 1448: Count Good Nodes in Binary Tree (DFS with Path Maximum)

2026-05-08 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 1448Binary TreeDFS

Today we solve LeetCode 1448 - Count Good Nodes in Binary Tree.

Source: https://leetcode.com/problems/count-good-nodes-in-binary-tree/

English

Problem Summary

A node X in the tree is good if on the path from root to X, there is no node with a value greater than X.

Key Insight

During DFS, keep the maximum value seen on the current root-to-node path. A node is good if node.val >= pathMax.

Complexity Analysis

Time: O(n), each node visited once. Space: O(h) recursion stack.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }
    private int dfs(TreeNode node, int pathMax) {
        if (node == null) return 0;
        int good = node.val >= pathMax ? 1 : 0;
        int nextMax = Math.max(pathMax, node.val);
        return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
    }
}

func goodNodes(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, pathMax int) int {
        if node == nil { return 0 }
        good := 0
        if node.Val >= pathMax { good = 1 }
        nextMax := pathMax
        if node.Val > nextMax { nextMax = node.Val }
        return good + dfs(node.Left, nextMax) + dfs(node.Right, nextMax)
    }
    return dfs(root, -1<<31)
}

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }
    int dfs(TreeNode* node, int pathMax) {
        if (!node) return 0;
        int good = node->val >= pathMax ? 1 : 0;
        int nextMax = max(pathMax, node->val);
        return good + dfs(node->left, nextMax) + dfs(node->right, nextMax);
    }
};

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, path_max):
            if not node:
                return 0
            good = 1 if node.val >= path_max else 0
            nxt = max(path_max, node.val)
            return good + dfs(node.left, nxt) + dfs(node.right, nxt)
        return dfs(root, float('-inf'))

var goodNodes = function(root) {
  const dfs = (node, pathMax) => {
    if (!node) return 0;
    const good = node.val >= pathMax ? 1 : 0;
    const nextMax = Math.max(pathMax, node.val);
    return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
  };
  return dfs(root, -Infinity);
};

中文

题目概述

若从根到当前节点路径上不存在比当前节点值更大的节点，则该节点为 good node。

核心思路

DFS 遍历时维护路径最大值 pathMax。若 node.val >= pathMax，则答案加一，并把新路径最大值传给子节点。

复杂度分析

时间复杂度 O(n)，空间复杂度 O(h)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }
    private int dfs(TreeNode node, int pathMax) {
        if (node == null) return 0;
        int good = node.val >= pathMax ? 1 : 0;
        int nextMax = Math.max(pathMax, node.val);
        return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
    }
}

func goodNodes(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, pathMax int) int {
        if node == nil { return 0 }
        good := 0
        if node.Val >= pathMax { good = 1 }
        nextMax := pathMax
        if node.Val > nextMax { nextMax = node.Val }
        return good + dfs(node.Left, nextMax) + dfs(node.Right, nextMax)
    }
    return dfs(root, -1<<31)
}

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }
    int dfs(TreeNode* node, int pathMax) {
        if (!node) return 0;
        int good = node->val >= pathMax ? 1 : 0;
        int nextMax = max(pathMax, node->val);
        return good + dfs(node->left, nextMax) + dfs(node->right, nextMax);
    }
};

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, path_max):
            if not node:
                return 0
            good = 1 if node.val >= path_max else 0
            nxt = max(path_max, node.val)
            return good + dfs(node.left, nxt) + dfs(node.right, nxt)
        return dfs(root, float('-inf'))

var goodNodes = function(root) {
  const dfs = (node, pathMax) => {
    if (!node) return 0;
    const good = node.val >= pathMax ? 1 : 0;
    const nextMax = Math.max(pathMax, node.val);
    return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
  };
  return dfs(root, -Infinity);
};