leetcode

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

kth-smallest.py (757B)

      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 
      9 # IDEA:
     10 
     11 # Perform DFS:
     12 # go all the way to the left
     13 # decrement smallest counter value
     14 # if smallest counter value == 0:
     15 # return current value
     16 
     17 
     18 class Solution:
     19     def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
     20         return dfs_kth(root, [k])
     21 
     22 
     23 def dfs_kth(root, val):
     24 
     25     if root is None:
     26         return None
     27 
     28     left_found = dfs_kth(root.left, val)
     29 
     30     if left_found is not None:
     31         return left_found
     32 
     33     val[0] -= 1
     34 
     35     if val[0] == 0:
     36         return root.val
     37 
     38     right_found = dfs_kth(root.right, val)
     39 
     40     return right_found