在 Python 中根据前序和后序遍历构建二叉树
pythonserver side programmingprogramming
假设我们有两个遍历序列:前序和后序，我们必须根据这两个序列生成二叉树。因此，如果序列为 [1,2,4,5,3,6,7]、[4,5,2,6,7,3,1]，则输出将是
为了解决这个问题，我们将遵循以下步骤 −
- ans := 通过取值 pre[0] 创建树节点，stack := 空堆栈，并插入 ans
- i := 1 and j := 0
- while i < length of pre and j <帖子的长度
- 如果栈顶值 = post[j]，则将 j 增加 1，从堆栈中弹出，然后进行下一次迭代
- node := 创建一个值为 pre[i] 的树节点
- 如果栈顶节点的左侧部分为空，则将栈顶节点的左侧设置为节点，否则将栈顶节点的右侧设置为节点
- 将节点插入堆栈
- 将 i 增加 1
- 返回答案
让我们看看下面的实现以便更好地理解 −
示例
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def height(root):
if root is None:
return 0
else :
# 计算左、右子树的高度
l_height = height(root.left)
r_height = height(root.right)
# 找到较大的一个，并返回它
if l_height > r_height :
return l_height+1
else:
return r_height+1
def print_given_level(root, level):
if root is None:
return
if level == 1:
print(root.data,end = ',')
elif level > 1 :
print_given_level(root.left , level-1)
print_given_level(root.right , level-1)
def level_order(root):
print('[', end = '')
h = height(root)
for i in range(1, h+1):
print_given_level(root, i)
print(']')
class Solution(object):
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
ans = TreeNode(pre[0])
stack = [ans]
i = 1
j = 0
while i < len(pre) and j < len(post):
if stack[-1].data == post[j]:
j+=1
stack.pop(-1)
continue
node = TreeNode(pre[i])
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
i+=1
return ans
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree)
输入
[1,2,4,5,3,6,7] [4,5,2,6,7,3,1] pre = [1,2,4,5,3,6,7] post = [4,5,2,6,7,3,1]
输出
[1,2,3,4,5,6,7,]
