# coding: utf-8'''題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。'''class Node:  def __init__(self, data, left, right):    self.data = data    self.left = left    self.right = rightdef construct_tree(pre_order, mid_order):  # 忽略參數合法性判斷  if len(pre_order) == 0 :    return None  # 前序遍歷的第一個結點一定是根結點  root_data = pre_order[0]  for i in range(0, len(mid_order)):    if mid_order[i] == root_data:      break  # 遞歸構造左子樹和右子樹  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