1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| import collections from typing import Optional
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def array_to_binary_tree(arr:list)-> Optional[TreeNode]: """ 将数组转换为二叉树(层次遍历方式) :param arr: 输入数组,None 表示空节点,例如 [1, 2, 3, None, 4] :return: 二叉树根节点 """ if not arr: return None root = TreeNode(arr[0]) queue = collections.deque([root]) index = 1 while queue and index < len(arr): node = queue.popleft() if index < len(arr) and arr[index] is not None: node.left = TreeNode(arr[index]) queue.append(node.left) index += 1 if index < len(arr) and arr[index] is not None: node.right = TreeNode(arr[index]) queue.append(node.right) index += 1 return root
def level_order(root:Optional[TreeNode]) -> Optional[TreeNode]: result = [] q = collections.deque([root]) while q: node = q.popleft() if node: result.append(node.val) q.append(node.left) q.append(node.right) else: result.append(None) while result and result[-1] is None: result.pop() return result
if __name__ == "__main__": test_array = [1, 2, 3, 4, 5, None, 6] root = array_to_binary_tree(test_array) print("输入数组:", test_array) print("层次遍历:", level_order(root))
|