COUNT NODES EQUAL TO AVERAGE OF SUBTREE | LEETCODE 2265 | PYTHON DFS SOLUTION
Vložit
- čas přidán 24. 07. 2024
- Channel Discord Community: / discord
Problem Link:leetcode.com/problems/count-n...
Today we are solving a tree question from Google which follows a very familiar pattern: Post-Order DFS with some sort of processing at each level of the recursion stack. We've done a ton of these on the channel before so shouldn't be an issue figuring this one out!
TIMESTAMPS:
00:00 Intro
00:10 Question Prompt
00:35 Basic Example & Solution Intuition
05:29 Coding
10:05 Time/Space Complexity
11:15 Outro - Věda a technologie
This is my current favorite channel! Love your explanations :) I was able to code it myself after listening to your explanation!❤
class Solution:
def averageOfSubtree(self, root: TreeNode) -> int:
# do a postorder
count = [0]
def dfs(node):
if not node: return (0, 0) #sum, no.of nodes
val_l, count_l = dfs(node.left)
val_r, count_r = dfs(node.right)
total_val = node.val + val_l + val_r
total_count = 1+count_l+count_r
avg = total_val // total_count
if node.val == avg:
count[0]+=1
return (total_val, total_count)
dfs(root)
return count[0]
Amazing solution. Wish you the best!
I bombed this question because i never seen recursion returning tuple pattern before
Yea it's a strange one, But once you realise you can return whatever you want from it then it allows you to get creative and solve a lot of these more easily
why self for variable types?