I'd recommend to make "count" and "ans" member variables and access them using self.count and self.ans instead of that list hack. It's more clear on what is going on and is easier to explain to an interviewer
In Python, if you just used variables, then when you update the values in any particular recursive call, that variable technically isn't available and you will get an error because you defined the variable outside of the the scope of that local recursive call. If you put the value as an element of an array, it has a global memory address that is accessible regardless of which recursive call you are in. Greg goes over this in his Diameter of Binary Tree video: ua-cam.com/video/6lJZ_xj1mEo/v-deo.html
Here is the solution I come up with after watching your explanation: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: result = [] def dfs(root): if not root:return None dfs(root.left) result.append(root.val) dfs(root.right) dfs(root) return result[k-1]
This should be more simpler to understand: class Solution(object): def kthSmallest(self, root, k): res=[] def dfs(root): if not root: return dfs(root.left) res.append(root.val) dfs(root.right) dfs(root) return res[k-1]
Master Data Structures & Algorithms For FREE at AlgoMap.io!
I'd recommend to make "count" and "ans" member variables and access them using self.count and self.ans instead of that list hack. It's more clear on what is going on and is easier to explain to an interviewer
Such an amazing content ❤
Can you make unique binary search tree problem next
Thank you so much! Maybe I'll see :)
Why use count = [k] and ans = [0] instead of just k or 0. Why use a single element list there?
Same question
In Python, if you just used variables, then when you update the values in any particular recursive call, that variable technically isn't available and you will get an error because you defined the variable outside of the the scope of that local recursive call. If you put the value as an element of an array, it has a global memory address that is accessible regardless of which recursive call you are in. Greg goes over this in his Diameter of Binary Tree video: ua-cam.com/video/6lJZ_xj1mEo/v-deo.html
@@Infinitely16 Thanks very much for the detailed explanation! I will go over the video
just use self.count and self.ans not this odd workaround, that'd be a weird thing to explain in an interview
@@Philgob right! self variables have global access too
Amazing content. Can you make video on 105. Construct Binary Tree from Preorder and Inorder Traversal? Tks
I'll try
The time complexity is O(N) or is it O(H+K) ?
Here is the solution I come up with after watching your explanation: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
result = []
def dfs(root):
if not root:return None
dfs(root.left)
result.append(root.val)
dfs(root.right)
dfs(root)
return result[k-1]
why not using nonlocal ?
This should be more simpler to understand:
class Solution(object):
def kthSmallest(self, root, k):
res=[]
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res[k-1]
@@GarouNguyen because the list is 0-indexed, so if he wants the element 5 of the list he needs to use the element: res[5-1]
this forces you to visit the whole tree, it's accepted on leetcode but worse even tho complexity is the same (imagine massive tree and k = 1000000)
Heap sort