Leetcode里和二叉树相关的题目,都是用一个数组表示二叉树的,而这个数组是按照层次优先顺序给出的,连其中的空结点也表示了出来,刚好就是2^N-1个结点,N表示层数。
但数组毕竟无法和二叉树一样具有链式结构,无法进行算法测试,因此尝试直接通过这样的数组构建二叉树。
通过数组创建这样的二叉树,也通过层次优先构建。和遍历一样,都利用队列结构去迭代。
from collections import deque class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def __eq__(self, other): return self.val == other.val def __str__(self): return str(self.val) def build_bitree_fromarray(root_array): root_node = None if len(root_array) > 0: root_node = TreeNode(root_array[0]) ind = 0 dq = deque() dq.append(root_node) while len(dq) > 0: pre_node = dq.popleft() # print(f"{ind} -> ({(ind << 1) + 1}, {(ind << 1) + 2}) :: {root_array[ind]} -> ({root_array[(ind << 1) + 1]}, {root_array[(ind << 1) + 2]})") if (ind << 1) + 1 < len(root_array): if root_array[(ind << 1) + 1] != -1: tmp_node = TreeNode(root_array[(ind << 1) + 1]) dq.append(tmp_node) pre_node.left = tmp_node if (ind << 1) + 2 < len(root_array): if root_array[(ind << 1) + 2] != -1: tmp_node = TreeNode(root_array[(ind << 1) + 2]) dq.append(tmp_node) pre_node.right = tmp_node ind += 1 return root_node if __name__ == '__main__': root = [3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4] root_node = build_bitree_fromarray(root_array=root) print_tree_level(root_node)
打印也可以通过层次优先打印,要在创建的时候标记每一个结点的层数。
标签:__,self,二叉树,数组,ind,root,Leetcode From: https://www.cnblogs.com/zhaoke271828/p/18119092