forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathconstruct_tree_postorder_preorder.py
More file actions
109 lines (80 loc) · 2.89 KB
/
construct_tree_postorder_preorder.py
File metadata and controls
109 lines (80 loc) · 2.89 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
"""
Construct Tree from Preorder and Postorder Traversal
Given preorder and postorder traversals of a full binary tree, construct the
tree and return its inorder traversal. A full binary tree has either zero or
two children per node.
Reference: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees
Complexity:
Time: O(n^2) due to linear search in postorder array
Space: O(n) for the constructed tree
"""
from __future__ import annotations
from algorithms.common.tree_node import TreeNode
pre_index = 0
def construct_tree_util(
pre: list[int], post: list[int], low: int, high: int, size: int
) -> TreeNode | None:
"""Recursively construct a binary tree from preorder and postorder arrays.
Uses a global pre_index to track the current position in the preorder
array during recursive construction.
Args:
pre: The preorder traversal array.
post: The postorder traversal array.
low: The lower bound index in the postorder array.
high: The upper bound index in the postorder array.
size: The total number of elements.
Returns:
The root of the constructed subtree, or None if bounds are invalid.
Examples:
>>> construct_tree_util([1, 2, 3], [2, 3, 1], 0, 2, 3) is not None
True
"""
global pre_index
if pre_index == -1:
pre_index = 0
if pre_index >= size or low > high:
return None
root = TreeNode(pre[pre_index])
pre_index += 1
if low == high or pre_index >= size:
return root
i = low
while i <= high:
if pre[pre_index] == post[i]:
break
i += 1
if i <= high:
root.left = construct_tree_util(pre, post, low, i, size)
root.right = construct_tree_util(pre, post, i + 1, high, size)
return root
def construct_tree(pre: list[int], post: list[int], size: int) -> list[int]:
"""Construct a full binary tree and return its inorder traversal.
Args:
pre: The preorder traversal array.
post: The postorder traversal array.
size: The number of elements.
Returns:
A list of values representing the inorder traversal of the
constructed tree.
Examples:
>>> construct_tree([1, 2, 4, 5, 3, 6, 7], [4, 5, 2, 6, 7, 3, 1], 7)
[4, 2, 5, 1, 6, 3, 7]
"""
root = construct_tree_util(pre, post, 0, size - 1, size)
return _inorder(root)
def _inorder(root: TreeNode | None, result: list[int] | None = None) -> list[int]:
"""Return the inorder traversal of a binary tree.
Args:
root: The root of the tree to traverse.
result: Accumulator list for the traversal values.
Returns:
A list of node values in inorder sequence.
"""
if root is None:
return []
if result is None:
result = []
_inorder(root.left, result)
result.append(root.val)
_inorder(root.right, result)
return result