Cousins in Binary Tree II - Leetcode 2641 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:46 - Coding Explanation

leetcode 2641

#neetcode #leetcode #python

[__kasim__khan__]

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.

[alittlecoding]

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

[jamestwosheep]

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.

[rahuljaiswal]

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

[superray]

as good as always! Hope you can also release a version for DFS since it will optimize the memory complexity

[MP-nyep]

Thank you so much for the daily leetcode!

[hetparekh]

Came up with the same logic and mindset, but came here to optimise it further ♥

[junjason]

My one-pass BFS solution.

class Solution:
def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = deque([(root, root.val)])
while queue:
depth_sum = sum(node.val for node, _ in queue)
for _ in range(len(queue)):
node, siblings_sum = queue.popleft()
node.val = depth_sum - siblings_sum
child_siblings_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
if node.left:
queue.append((node.left, child_siblings_sum))
if node.right:
queue.append((node.right, child_siblings_sum))

return root