leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

count-good.py (774B)

      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
      7 
      8 # basic dfs problem
      9 # pass forwards largest seen
     10 # if > largest seen update largest seen and increment counter
     11 # else continue with children
     12 
     13 
     14 class Solution:
     15     def goodNodes(self, root: TreeNode) -> int:
     16         return dfs_count_good(root, -100000)
     17 
     18 
     19 def dfs_count_good(root, highest_val) -> int:
     20 
     21     if root is None:
     22         return 0
     23 
     24     new_high = max(root.val, highest_val)
     25     left = dfs_count_good(root.left, new_high)
     26     right = dfs_count_good(root.right, new_high)
     27 
     28     if root.val >= highest_val:
     29         return left + right + 1
     30     else:
     31         return left + right