Python重建二叉树

本文阅读 2 分钟
首页 Python笔记 正文

利用二叉树前序遍历和中序遍历的特性。前序遍历的第一个值一定为根节点,对应于中序遍历中间的一个点。在中序遍历序列中,这个点左侧的均为根的左子树,这个点右侧的均为根的右子树。这时可以利用递归,分别取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树继续上一个过程,取前序遍历[i+1:]和中序遍历[i+1]对应于右子树继续上一个过程,最终得以重建二叉树。

  1. '''
  2. 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。
  3. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  4. 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
  5. '''
  6. # -*- coding:utf-8 -*-
  7. class TreeNode:
  8. def __init__(self, x):
  9. self.val = x
  10. self.left = None
  11. self.right = None
  12. class Solution:
  13. # 返回构造的TreeNode根节点
  14. def reConstructBinaryTree(self, pre, tin):
  15. # write code here
  16. if not pre and not tin:
  17. return None
  18. root = TreeNode(pre[0])
  19. if set(pre) != set(tin):
  20. return None
  21. i = tin.index(pre[0])
  22. root.left = self.reConstructBinaryTree(pre[1:i+1], tin[:i])
  23. root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
  24. return root
  25. pre = [1, 2, 3, 5, 6, 4]
  26. tin = [5, 3, 6, 2, 4, 1]
  27. test = Solution()
  28. newTree = test.reConstructBinaryTree(pre, tin)
  29. # 按层序遍历输出树中某一层的值
  30. def PrintNodeAtLevel(treeNode, level):
  31. if not treeNode or level < 0:
  32. return 0
  33. if level == 0:
  34. print(treeNode.val)
  35. return 1
  36. PrintNodeAtLevel(treeNode.left, level-1)
  37. PrintNodeAtLevel(treeNode.right, level-1)
  38. # 已知树的深度按层遍历输出树的值
  39. def PrintNodeByLevel(treeNode, depth):
  40. for level in range(depth):
  41. PrintNodeAtLevel(treeNode, level)
  42. # # 不知道树的深度直接按层遍历输出树的值
  43. ####有bug, 待修复
  44. # def PrintNodeByLevel2(treeNode):
  45. # level = 0
  46. # while 1:
  47. # if not PrintNodeAtLevel(treeNode, level):
  48. # break
  49. # level = level + 1
  50. PrintNodeByLevel(newTree, 5)
  51. # PrintNodeByLevel2(newTree)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

python从头到尾打印链表
« 上一篇 01-21
Python用两个栈实现队列
下一篇 » 01-21

发表评论