count_good_nodes_in_binary_tree
1from math import inf 2from utils import TreeNode 3 4 5# @leet start 6# Definition for a binary tree node. 7# class TreeNode: 8# def __init__(self, val=0, left=None, right=None): 9# self.val = val 10# self.left = left 11# self.right = right 12class Solution: 13 def goodNodes(self, root: TreeNode) -> int: 14 """ 15 This function counts the nodes in a tree where on the path from root to X 16 there are no nodes with a value greater than X. 17 18 We do this by dfsing through the tree, counting the maximum value we've seen 19 so far. If we haven't seen a value greater than the current node, we add 1 20 to the count. 21 22 For the left and right nodes, we want to maximize the value we've seen, 23 so if we see a new greater node, we'll use that as the new max so far, 24 otherwise, we'll use the old max. 25 26 At the end after counting we end up with the correct amount of good nodes. 27 """ 28 count = 0 29 30 def dfs(node, max_so_far): 31 nonlocal count 32 if max_so_far <= node.val: 33 count += 1 34 if node.right: 35 dfs(node.right, max(max_so_far, node.val)) 36 if node.left: 37 dfs(node.left, max(max_so_far, node.val)) 38 39 dfs(root, -inf) 40 return count 41 42 43# @leet end 44 45 46def test(): 47 assert 2 + 2 == 4
class
Solution:
13class Solution: 14 def goodNodes(self, root: TreeNode) -> int: 15 """ 16 This function counts the nodes in a tree where on the path from root to X 17 there are no nodes with a value greater than X. 18 19 We do this by dfsing through the tree, counting the maximum value we've seen 20 so far. If we haven't seen a value greater than the current node, we add 1 21 to the count. 22 23 For the left and right nodes, we want to maximize the value we've seen, 24 so if we see a new greater node, we'll use that as the new max so far, 25 otherwise, we'll use the old max. 26 27 At the end after counting we end up with the correct amount of good nodes. 28 """ 29 count = 0 30 31 def dfs(node, max_so_far): 32 nonlocal count 33 if max_so_far <= node.val: 34 count += 1 35 if node.right: 36 dfs(node.right, max(max_so_far, node.val)) 37 if node.left: 38 dfs(node.left, max(max_so_far, node.val)) 39 40 dfs(root, -inf) 41 return count
14 def goodNodes(self, root: TreeNode) -> int: 15 """ 16 This function counts the nodes in a tree where on the path from root to X 17 there are no nodes with a value greater than X. 18 19 We do this by dfsing through the tree, counting the maximum value we've seen 20 so far. If we haven't seen a value greater than the current node, we add 1 21 to the count. 22 23 For the left and right nodes, we want to maximize the value we've seen, 24 so if we see a new greater node, we'll use that as the new max so far, 25 otherwise, we'll use the old max. 26 27 At the end after counting we end up with the correct amount of good nodes. 28 """ 29 count = 0 30 31 def dfs(node, max_so_far): 32 nonlocal count 33 if max_so_far <= node.val: 34 count += 1 35 if node.right: 36 dfs(node.right, max(max_so_far, node.val)) 37 if node.left: 38 dfs(node.left, max(max_so_far, node.val)) 39 40 dfs(root, -inf) 41 return count
This function counts the nodes in a tree where on the path from root to X there are no nodes with a value greater than X.
We do this by dfsing through the tree, counting the maximum value we've seen so far. If we haven't seen a value greater than the current node, we add 1 to the count.
For the left and right nodes, we want to maximize the value we've seen, so if we see a new greater node, we'll use that as the new max so far, otherwise, we'll use the old max.
At the end after counting we end up with the correct amount of good nodes.
def
test():