題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果越妈，請重建出該二叉樹搬卒。假設輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字结序。
這道題比較容易弯院，前序遍歷的結(jié)果中辱士，第一個結(jié)點一定是根結(jié)點，然后在中序遍歷的結(jié)果中查找這個根結(jié)點听绳，根結(jié)點左邊的就是左子樹颂碘，根結(jié)點右邊的就是右子樹，遞歸構(gòu)造出左椅挣、右子樹即可头岔。示意圖如圖所示：
# coding: utf-8
'''
題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果塔拳，請重建出該二叉樹。
假設輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字峡竣。
'''
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def construct_tree(pre_order, mid_order):
# 忽略參數(shù)合法性判斷
if len(pre_order) == 0 :
return None
# 前序遍歷的第一個結(jié)點一定是根結(jié)點
root_data = pre_order[0]
for i in range(0, len(mid_order)):
if mid_order[i] == root_data:
break
# 遞歸構(gòu)造左子樹和右子樹
left = construct_tree(pre_order[1 : 1 + i], mid_order[:i])
right = construct_tree(pre_order[1 + i:], mid_order[i+1:])
return Node(root_data, left, right)
if __name__ == '__main__':
pre_order = [1, 2, 4, 7, 3, 5, 6, 8]
mid_order = [4, 7, 2, 1, 5, 3, 8, 6]
root = construct_tree(pre_order, mid_order)
print root.data
print root.left.data
print root.right.data
print root.left.left.data
print root.left.left.right.data
print root.right.right.left
print root.right.left.data
