Leetcode 1448 Count Good Nodes in Binary Tree

Soru

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Örnek 1

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Örnek 2

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Örnek 3

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Çözüm

• Bir binary tree (ikili ağaç) veriliyor. Bu ağaçta “good node” olarak adlandırılan düğümler şunlardır:Root’tan o düğüme giden yolda, değeri kendisinden büyük olan bir düğüm yoksa, o düğüm “good node”‘dur.
• Bu soruda, DFS (Depth First Search - Derinlik Öncelikli Arama) kullanabiliriz.
• Her düğümde, o ana kadar gördüğümüz maksimum değeri tutarız.
• Eğer şu anki düğümün değeri, bu maksimum değerden büyük veya eşitse → good node’dur.
• Not:DFS yerine BFS ile de yapılabilir ama DFS daha doğal hissettiriyor bu tarz root-to-node yol takibi gereken sorularda.DFS ile birlikte sürekli bir “max so far” taşıdığımız için ekstra veri yapısına ihtiyaç yok.

Code

class Solution:
    def goodNodes(self, root):
        def dfs(node, max_val):
            if not node:
                return 0
            
            # Bu düğüm good node mu?
            good = 1 if node.val >= max_val else 0
            
            # Yeni maksimumu hesapla
            new_max = max(max_val, node.val)
            
            # Sol ve sağ çocuklara git
            good += dfs(node.left, new_max)
            good += dfs(node.right, new_max)
            
            return good
        
        return dfs(root, root.val)

Complexity

• Time complexity (Zaman Karmaşıklığı): O(N) → Her düğüm bir kez ziyaret edilir

• Space complexity (Alan Karmaşıklığı): O(H) → H = ağacın yüksekliği (stack derinliği, balanced ise O(logN))