二元樹
用前序和中序建立第一棵樹，用中序和後序建立第二棵樹，在把兩棵樹合併(第三棵樹)，輸出第三棵樹的前、中、後序 模擬試題/俊賓出的/模擬測驗-3/3-1.py
前序和中序 構建 後序
python
import sys
def dfs(mid):
for i in before:
if i in mid:
ans.insert(0, i)
left = mid[:mid.index(i)]
right = mid[mid.index(i)+1:]
break
# 先跑右邊再跑左邊
if right:
dfs(right)
if left:
dfs(left)
for line in sys.stdin.read().splitlines():
before, mid = line.split() # 前序 , 中序
ans = []
dfs(mid)
print(''.join(ans))python
def dfs(before, mid):
if not before:
return []
root = before[0]
root_index = mid.index(root)
left_postorder = dfs(before[1:root_index+1], mid[:root_index])
right_postorder = dfs(before[root_index+1:], mid[root_index+1:])
return left_postorder + right_postorder + [root]
before = [3, 9, 20, 15, 7] # 前序
mid = [9, 3, 15, 20, 7] # 中序
postorder = dfs(before, mid)
print(postorder) # 输出后序遍历序列中序和後序 構建 前序
python
def dfs(mid, after):
if not mid:
return []
root = after[-1]
root_index = mid.index(root)
left_preorder = dfs(mid[:root_index], after[:root_index])
right_preorder = dfs(mid[root_index+1:], after[root_index:-1])
return [root] + left_preorder + right_preorder
mid = [9, 3, 15, 20, 7]
after = [9, 15, 7, 20, 3]
preorder = dfs(mid, after)
print(preorder) # 输出前序遍历序列python
import sys
def dfs(mid, post):
if not mid or not post:
return
root_val = post.pop()
ans.append(root_val)
root_idx = mid.index(root_val)
right_mid = mid[root_idx + 1:]
left_mid = mid[:root_idx]
right_post = post[len(right_mid):]
left_post = post[:len(left_mid)]
dfs(right_mid, right_post)
dfs(left_mid, left_post)
for line in sys.stdin.read().splitlines():
mid, post = line.split() # 中序, 後序
ans = []
dfs(mid, list(post))
print(''.join(ans))前序和後序 構建 中序
小技巧
如果想要輸入 前序和後序 構建 中序
在特定情況 左右子樹長滿的情況下 前後也可以推回原來的樹
你畫一棵樹 然後分別把前中後寫出來 就會找到感覺了 光看數字無感 就再把 前中後的定義寫上去比對
建立二元樹
python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_node(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert_node(root.left, value)
else:
root.right = insert_node(root.right, value)
return root
def print_tree(root):
if root is not None:
result.append(root.value)
if root.left is not None or root.right is not None:
print_tree(root.left)
print_tree(root.right)
ary = list(map(int, input().split()))
root = None
for num in ary:
root = insert_node(root, num)
result = []
print_tree(root)
print(' '.join(map(str, result)))Contributors
lucashsu95