Python把给定的列表转化成二叉树，, 在LeetCo

Python把给定的列表转化成二叉树，, 在LeetCo

在LeetCode上做题时，有很多二叉树相关题目的测试数据是用列表给出的，提交的时候有时会出现一些数据通不过，这就需要在本地调试，因此需要使用列表来构建二叉树，方便自己调试。LeetCode上二叉树结点的定义如下：

1 class TreeNode(object):2     def __init__(self, x):3         self.val = x4         self.left = None5         self.right = None

使用列表构建二叉树，以及二叉树的层次遍历，先序遍历，中序遍历，后序遍历的代码如下所示：

 1 from collections import deque 2  3  4 class Tree(object): 5     def __init__(self): 6         self.root = None 7      8     def construct_tree(self, values=None): 9         if not values:10             return None11         self.root = TreeNode(values[0])12         queue = deque([self.root])13         leng = len(values)14         nums = 115         while nums < leng:16             node = queue.popleft()17             if node:18                 node.left = TreeNode(values[nums]) if values[nums] else None19                 queue.append(node.left)20                 if nums + 1 < leng:21                     node.right = TreeNode(values[nums+1]) if values[nums+1] else None22                     queue.append(node.right)23                     nums += 124                 nums += 125     26     def bfs(self):27         ret = []28         queue = deque([self.root])29         while queue:30             node = queue.popleft()31             if node:32                 ret.append(node.val)33                 queue.append(node.left)34                 queue.append(node.right)35         return ret36 37     def pre_traversal(self):38         ret = []39 40         def traversal(head):41             if not head:42                 return43             ret.append(head.val)44             traversal(head.left)45             traversal(head.right)46         traversal(self.root)47         return ret48 49     def in_traversal(self):50         ret = []51 52         def traversal(head):53             if not head:54                 return55             traversal(head.left)56             ret.append(head.val)57             traversal(head.right)58 59         traversal(self.root)60         return ret61 62     def post_traversal(self):63         ret = []64 65         def traversal(head):66             if not head:67                 return68             traversal(head.left)69             traversal(head.right)70             ret.append(head.val)71 72         traversal(self.root)73         return ret

测试以及使用：

1 t = Tree()2 t.construct_tree([1, 2, None, 4, 3, None, 5])3 print t.bfs()4 print t.pre_traversal()5 print t.in_traversal()6 print t.post_traversal()

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