2023年6月22日发(作者：)

Python把给定的列表转化成⼆叉树

在LeetCode上做题时，有很多⼆叉树相关题⽬的测试数据是⽤列表给出的，提交的时候有时会出现⼀些数据通不过，这就需要在本地调试，因此需要使⽤列表来构建⼆叉树，⽅便⾃⼰调试。LeetCode上⼆叉树结点的定义如下：1 class TreeNode(object):2 def __init__(self, x):3 = x4 = None5 = None

使⽤列表构建⼆叉树，以及⼆叉树的层次遍历，先序遍历，中序遍历，后序遍历的代码如下所⽰： 1 from collections import deque 2

3

4 class Tree(object): 5 def __init__(self): 6 = None 7

8 def construct_tree(self, values=None): 9 if not values:10 return None11 = TreeNode(values[0])12 queue = deque([])13 leng = len(values)14 nums = 115 while nums < leng:16 node = t()17 if node:18 = TreeNode(values[nums]) if values[nums] else None19 ()20 if nums + 1 < leng:21 = TreeNode(values[nums+1]) if values[nums+1] else None22 ()23 nums += 124 nums += 125

26 def bfs(self):27 ret = []28 queue = deque([])29 while queue:30 node = t()31 if node:32 ()33 ()34 ()35 return ret36

37 def pre_traversal(self):38 ret = []39

40 def traversal(head):41 if not head:42 return43 ()44 traversal()45 traversal()46 traversal()47 return ret48

49 def in_traversal(self):50 ret = []51

52 def traversal(head):53 if not head:54 return55 traversal()56 ()57 traversal()58

59 traversal()60 return ret61

62 def post_traversal(self):63 ret = []64

65 def traversal(head):66 if not head:67 return68 traversal()69 traversal()70 ()71

72 traversal()73 return ret

测试以及使⽤：1 t = Tree()2 uct_tree([1, 2, None, 4, 3, None, 5])3 print ()4 print _traversal()5 print _traversal()6 print _traversal()