Repository navigation
Expand file tree
/
Copy pathencode_decode_tree.py
More file actions
61 lines (44 loc) · 1.58 KB
/
Copy pathencode_decode_tree.py
File metadata and controls
61 lines (44 loc) · 1.58 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
"""Encode / Decode Tree.
Encode an n-ary tree to a binary tree and decode it back to a matching n-ary tree.
"""
from collections import deque
from src.binary_tree.tree_node import TreeNode
from src.n_ary_tree.nary_tree_node import NaryTreeNode
def encode(root: NaryTreeNode) -> TreeNode | None:
"""Encode an n-ary tree into a binary tree using a left-child/right-sibling representation."""
if not root:
return None
root_node = TreeNode(root.value)
queue = deque([(root_node, root)])
while queue:
parent, current = queue.popleft()
previous = None
head = None
if current.children:
for child in current.children:
node = TreeNode(child.value)
if previous:
previous.right = node
else:
head = node
previous = node
queue.append((node, child))
parent.left = head
return root_node
def decode(data: TreeNode) -> NaryTreeNode | None:
"""Decode a binary tree produced by encode() back into a matching n-ary tree."""
if not data:
return None
root = NaryTreeNode(data.val, [])
queue = deque([(root, data)])
while queue:
parent, current = queue.popleft()
first_child = current.left
sibling = first_child
while sibling:
node = NaryTreeNode(sibling.val, [])
if parent.children is not None:
parent.children.append(node)
queue.append((node, sibling))
sibling = sibling.right
return root