NUMBER OF GOOD LEAF NODE PAIRS | PYTHON | LEETCODE # 1530
Вставка
- Опубліковано 7 вер 2024
- In this video we are solving a popular ByteDance interview question: Number of Good Leaf Node Pairs.
This is an annoying question that is a bit tricky to solve. It uses a postorder DFS traversal and requires some interesting processing on each node to derive the solution.
space is N, time should be n cube for your solution, as it's n square for each non-leaf nodes, i.e. n * n2 = n3.
thank you
Great explanation! Thanks a lot
Why do we use post order instead of in order traversal?
This isn't a Binary Search Tree, it's a binary tree, there's not concept of in-order traversal in this case.
Because, in post order we first travel the leaf nodes then the parents, that is what we wanted since we have to return the list to the parent.
I could not solve this problem, I came for help, teach me! P.S. I overcomplicated, I built an undirected graph and then it failed in case [1,1,1] :D code below
def countPairs(self, root: TreeNode, distance: int) -> int:
def traverse(node: TreeNode):
if not node:
return
if node.left:
graph[node.left.val].append(node.val)
graph[node.val].append(node.left.val)
traverse(node.left)
if node.right:
graph[node.right.val].append(node.val)
graph[node.val].append(node.right.val)
traverse(node.right)
if node.left is None and node.right is None:
q.append((node.val, 0))
graph = defaultdict(list)
q = deque() # node, steps
traverse(root)
result = 0
visited = set()
while q:
for _ in range(len(q)):
node, steps = q.popleft()
for nei in graph[node]:
if nei in visited or steps + 1 > distance:
continue
visited.add(nei)
if len(graph[nei]) == 1:
result += 1
else:
q.append((nei, steps + 1))
return result // 2 if result != 0 else 0