Binary Trees and BFS
863. All Nodes Distance K in Binary Tree
2 min readApr 15, 2020
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
if k==0:return [target.val]
parent = {}
def helper(nodea, nodeb):
if nodeb is not None:
parent[nodeb.val] = nodea
helper(nodeb, nodeb.left)
helper(nodeb, nodeb.right)
helper(root, root.left)
helper(root, root.right)
#print(parent)
def bfs(node):
res = []
from collections import deque
Q = deque([(target, 0)])
seen = {target.val}
while Q:
#print(Q)
node, d = Q.popleft()
#print(node, d)
for child_node in [node.left, node.right, parent[node.val] if node.val in parent else None]:
if child_node is not None and child_node.val not in seen and d+1<=k:
#print('*****',child_node.val)
seen.add(child_node.val)
if d+1==k:res.append(child_node.val)
elif d+1<k:
Q.append((child_node, d+1))
return res
return bfs(target)
A more concise way to do it
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
conn = collections.defaultdict(list)
def connect(parent, child):
if parent and child:
conn[parent.val].append(child.val)
conn[child.val].append(parent.val)
if child.left: connect(child, child.left)
if child.right: connect(child, child.right)
connect(None, root)
bfs = [target.val]
seen = set(bfs)
for i in range(k):
bfs = [y for x in bfs for y in conn[x] if y not in seen]
seen |= set(bfs)
return bfs
A nonconcise one
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
graph = collections.defaultdict(list)
if k==0:return [target.val]
def helper(parent, node):
if node is None:return
for child in [parent, node.left, node.right]:
if child is not None:
graph[node.val].append(child.val)
helper(node, node.left)
helper(node, node.right)
helper(None, root)
res = []
def bfs():
Q = collections.deque([(target.val, 0)])
seen = {target.val}
while Q:
val, dis = Q.popleft()
for neighbor in graph[val]:
if neighbor not in seen:
seen.add(neighbor)
if dis+1==k:res.append(neighbor)
else:
Q.append((neighbor, dis+1))
bfs()
return res# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if head is None:return None
tail = head
nodes = []
while tail is not None:
nodes.append(tail)
tail = tail.next
dummy = new_tail = ListNode(-1)
l, r = 0, len(nodes)-1
side = 0
while l<=r:
if side%2==0:
# left
new_tail.next = nodes[l]
new_tail = new_tail.next
l += 1
else:
new_tail.next = nodes[r]
new_tail = new_tail.next
r -= 1
side += 1
new_tail.next = None
return dummy.next
