1448. Count Good Nodes in Binary Tree

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def goodNodes(self, root: TreeNode) -> int:
 9        # bfs/dfs traversal with running_max_val
10
11        if not root:
12            return 0
13
14        dq = deque([(root, root.val)])  # node, max_val_seen
15        result = 0
16
17        while dq:
18            node, max_val = dq.popleft()
19            nv = node.val
20            if nv >= max_val:
21                result += 1
22                max_val = nv
23            if node.left:
24                dq.append((node.left, max_val))
25            if node.right:
26                dq.append((node.right, max_val))
27        
28        return result