I was able to do this in single BFS Traversal , I just kept the childrenSum for all nodes in current level , and kept changing that after every level finishes.
I like your elegant solution for this one! The solution I came up with had a single BFS pass, but involved assigning IDs to each node, using a hash map to keep track of which nodes belonged to which parent, and calculating a prefix sum and suffix sum array at each level. It turned out to be pretty efficient in terms of time and memory, but it was fairly complicated and I still feel a bit dumb for not recognising the much simpler approach in this video.
can be done in one pass class Solution: def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: pq = deque() pq.append((root.val, root)) while pq: n = len(pq) levelSum = 0 for localSum, node in pq: levelSum += node.val for i in range(n): localSum, node = pq.popleft() childSum = 0 if node.left: childSum += node.left.val if node.right: childSum += node.right.val if node.left: pq.append((childSum, node.left)) if node.right: pq.append((childSum, node.right)) node.val = levelSum - localSum return root
Cause he loves doing these videos, he has said multiple times. I can be consistent in drinking beer and eating chips too. But he is the GOAT thats for sure.
I was able to do this in single BFS Traversal , I just kept the childrenSum for all nodes in current level , and kept changing that after every level finishes.
I like your elegant solution for this one! The solution I came up with had a single BFS pass, but involved assigning IDs to each node, using a hash map to keep track of which nodes belonged to which parent, and calculating a prefix sum and suffix sum array at each level. It turned out to be pretty efficient in terms of time and memory, but it was fairly complicated and I still feel a bit dumb for not recognising the much simpler approach in this video.
can't believe i wrote the exact same code, came here to see if I did it in a stupid way or what. especially that double "if" part.
thanks
can be done in one pass
class Solution:
def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
pq = deque()
pq.append((root.val, root))
while pq:
n = len(pq)
levelSum = 0
for localSum, node in pq:
levelSum += node.val
for i in range(n):
localSum, node = pq.popleft()
childSum = 0
if node.left: childSum += node.left.val
if node.right: childSum += node.right.val
if node.left: pq.append((childSum, node.left))
if node.right: pq.append((childSum, node.right))
node.val = levelSum - localSum
return root
as good as always! Hope you can also release a version for DFS since it will optimize the memory complexity
how is this man so consistent
Maybe he's trying to get another job
Cause he loves doing these videos, he has said multiple times. I can be consistent in drinking beer and eating chips too. But he is the GOAT thats for sure.
Thank you so much for the daily leetcode!
Came up with the same logic and mindset , but came here to optimise it further ♥
How this handles no cousin case
if no cousin is present then the level sum would be the siblings sum and we are subtracting sibling sum from each child node so it becomes zero
What?
so fasssssssssssssssssssssssssst.
quite alabama problem
Bro late Today