1448. Count Good Nodes in Binary Tree

Medium
Description

給定一棵二元樹，如果從根到節點 X 的路徑上沒有任何節點的值大於 X，則稱 X 為「好節點」。回傳好節點的數量。

Example:

Input: root = [3,1,4,3,null,1,5] Output: 4 (好節點為 3, 3, 4, 5)

Intuition#

DFS 過程中傳遞「路徑上的最大值」，若當前節點值 >= 最大值，就是好節點。

  • 從根往下遍歷時維護一個「到目前為止的最大值」
  • 根節點一定是好節點（路徑上只有自己）

Approaches#

⭐ 1: Recursive DFS#

  • 概念: DFS 傳遞路徑最大值，當前節點值 >= 最大值時計數 +1
  • 時間複雜度: O(n)
  • 空間複雜度: O(h)
class Solution {
    fun goodNodes(root: TreeNode?): Int {
        return dfs(root, Int.MIN_VALUE)
    }

    private fun dfs(node: TreeNode?, maxSoFar: Int): Int {
        if (node == null) return 0
        val count = if (node.`val` >= maxSoFar) 1 else 0
        val newMax = maxOf(maxSoFar, node.`val`)
        return count + dfs(node.left, newMax) + dfs(node.right, newMax)
    }
}

2: Iterative DFS（Stack）#

  • 概念: 使用堆疊模擬 DFS，每個元素同時記錄節點和路徑最大值
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun goodNodes(root: TreeNode?): Int {
        if (root == null) return 0
        var count = 0
        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.addLast(root to Int.MIN_VALUE)
        while (stack.isNotEmpty()) {
            val (node, maxSoFar) = stack.removeLast()
            if (node.`val` >= maxSoFar) count++
            val newMax = maxOf(maxSoFar, node.`val`)
            node.left?.let { stack.addLast(it to newMax) }
            node.right?.let { stack.addLast(it to newMax) }
        }
        return count
    }
}

🔑 Takeaways#

  • Pattern: DFS 中傳遞額外狀態（路徑最大值、路徑和等）
  • 關鍵技巧: 將「路徑上的約束條件」轉化為遞迴參數，是處理路徑相關問題的通用技巧