資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中根據先序遍歷和後序遍歷構造二叉樹
假設我們有兩個遍歷序列：先序遍歷和後序遍歷，我們需要根據這兩個序列生成二叉樹。如果序列為 [1,2,4,5,3,6,7] 和 [4,5,2,6,7,3,1]，則輸出將為
為了解決這個問題，我們將遵循以下步驟：
- ans := 透過獲取 pre[0] 的值來建立一個樹節點，stack := 空棧，並將 ans 插入其中
- i := 1 和 j := 0
- 當 i < pre 的長度 且 j < post 的長度 時
- 如果棧頂值 = post[j]，則將 j 加 1，從棧中彈出，並進行下一次迭代
- node := 建立一個值為 pre[i] 的樹節點
- 如果棧頂節點的左子節點為空，則將棧頂節點的左子節點設定為 node，否則將棧頂節點的右子節點設定為 node
- 將 node 插入棧中
- 將 i 加 1
- 返回 ans
讓我們看看下面的實現，以便更好地理解：
示例
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 :
# Compute the height of left and right subtree
l_height = height(root.left)
r_height = height(root.right)
#Find the greater one, and return it
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,]
更新於: 2020-04-30
404 次檢視
廣告