Count Good Nodes in Binary Tree
Problem
https://leetcode.com/problems/count-good-nodes-in-binary-tree/
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.
Example 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.
Example 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.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Constraints:
The number of nodes in the binary tree is in the range
[1, 10^5].Each node’s value is between
[-10^4, 10^4].
Pattern
Tree, Depth-First Search, Breadth-First Search, Binary Tree
Approaches
Code
from __future__ import annotations
class TreeNode:
"""Node in a binary tree."""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
@classmethod
def from_list(cls, vals: list[int | None]) -> TreeNode | None:
if not vals:
return None
root = TreeNode(vals[0])
queue = [root]
i = 1
while i < len(vals):
node = queue.pop(0)
if i < len(vals) and vals[i] is not None:
node.left = TreeNode(vals[i])
queue.append(node.left)
i += 1
if i < len(vals) and vals[i] is not None:
node.right = TreeNode(vals[i])
queue.append(node.right)
i += 1
return root
def to_list(self) -> list:
result = []
queue = [self]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def good_nodes(node, max_val):
if node is None:
return 0
max_val = max(max_val, node.val)
result = 1 if node.val >= max_val else 0
result += good_nodes(node.left, max_val)
result += good_nodes(node.right, max_val)
return result
def goodNodes(root: TreeNode) -> int:
return good_nodes(root, root.val)
Test
>>> from count_good_nodes_in_binary_tree__dfs import goodNodes, TreeNode
>>> goodNodes(TreeNode.from_list([3, 1, 4, 3, None, 1, 5]))
4
>>> goodNodes(TreeNode.from_list([3, 3, None, 4, 2]))
3
- class count_good_nodes_in_binary_tree__dfs.TreeNode(val=0, left=None, right=None)
Bases:
objectNode in a binary tree.
- to_list() list
- count_good_nodes_in_binary_tree__dfs.good_nodes(node, max_val)