面试题６－－利用前序和中序遍历重构二叉树－－递归方法

  1. class TreeNode:
  2.     def __init__(self,data,left,right):
  3.         self.data=data
  4.         self.left=left
  5.         self.right=right
  6. 方法１
  7. def construct_tree(pre_order,mid_order):
  8. ##保证结点数不为０，该树才能重构
  9.     if (len(pre_order)==0) or (len(mid_order)==0):
  10.         return None
  11. ##根节点即为前序遍历的首元素
  12.     root_data=pre_order[0]# make sure the root_Data
     
  13. ##若结点个数为１，则不含左右子书
  14.     if len(pre_order)==1 :
  15.         return TreeNode(root_data,None,None)
  16. ##在中序遍历中查找根节点，确定其下标
  17.     for i in range(len(mid_order)):
  18.         if root_data==mid_order[i]:
  19.             break
  20.     root_mid_index=i
  21.     #if root_mid_index >0:
  22. ＃＃分别重构其左右子书    
  23.     left=construct_tree(pre_order[1:root_mid_index+1],mid_order[:root_mid_index])
  24.     if root_mid_index<len(mid_order):
  25.         right=construct_tree(pre_order[root_mid_index+1:],mid_order[root_mid_index+1:])
  26.     return TreeNode(root_data,left,right)
  27.     
  28. if __name__=='__main__':
  29.     pre_order = [1, 2, 4, 7, 3, 5, 6, 8]
  30.     mid_order = [4, 7, 2, 1, 5, 3, 8, 6]
  31.     root=construct_tree(pre_order,mid_order)

  1. 方法２
  2. #def reConstructBinaryTree(pre, tin):
  3. #    # write code here
  4. #    if (len(pre) == 0) or (len(tin) == 0):
  5. #        return None
  6. #    
  7. #    rootValue = pre[0]
  8. #    root = TreeNode(rootValue,None,None)
  9. #    if len(pre)==1:
  10. #        return root
  11. #    rootTinIndex = 0
  12. #    for i in range(len(tin)):
  13. #        if tin[i] == rootValue:
  14. #            rootTinIndex = i
  15. #    preStart = 1
  16. #    preEnd = rootTinIndex+1
  17. #    tinStart = 0
  18. #    tinEnd = rootTinIndex
  19. #    if rootTinIndex > 0:
  20. ＃＃用递归函数返回的结果赋值给某个变量　该变量之前必须定义过初值，如root.left/right==None
  21. #        root.left = reConstructBinaryTree(pre[preStart:preEnd], tin[tinStart:tinEnd])
  22. #    if rootTinIndex < len(pre):
  23. #        root.right = reConstructBinaryTree(pre[preEnd:], tin[tinEnd+1:])
  24. #    return root
  25. #if __name__=='__main__':
  26. #    pre = [1, 2, 4, 7, 3, 5, 6, 8]
  27. #    tin = [4, 7, 2, 1, 5, 3, 8, 6]
  28. #    root=reConstructBinaryTree(pre,tin)
  29.     print root.data
  30.     print root.left.data,root.right.data
  31.     print root.left.left.data,root.right.left.data,root.right.right.data
  32.     print root.left.left.right.data,root.right.right.left.data


附件列表

    【推广】 免费学中医，健康全家人
    原文地址：https://www.cnblogs.com/zzxx-myblog/p/6481263.html