如何用Python将极简表示的整数列表转换为二叉树？

你的原代码是基于完全二叉树的索引映射规则（父节点索引i对应子节点2i+1/2i+2），但LeetCode的二叉树列表表示规则是：

• 元素按层序遍历顺序填充，只有非None的节点才会占据树的位置
• 如果列表元素是None，表示该位置没有节点，不会为其分配后续的子节点位置

要实现符合该规则的转换，我们可以用广度优先搜索（BFS）队列来跟踪待分配子节点的父节点，具体实现如下：

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def array_to_binary_tree(array):
    if not array:
        return None
    
    # 初始化根节点和队列
    root = Node(array[0])
    queue = [root]
    ptr = 1  # 遍历列表的指针，从第二个元素开始
    
    while queue and ptr < len(array):
        parent = queue.pop(0)
        
        # 处理左子节点
        if ptr < len(array) and array[ptr] is not None:
            left_node = Node(array[ptr])
            parent.left = left_node
            queue.append(left_node)
        ptr += 1
        
        # 处理右子节点
        if ptr < len(array) and array[ptr] is not None:
            right_node = Node(array[ptr])
            parent.right = right_node
            queue.append(right_node)
        ptr += 1
    
    return root

代码说明 #

1. 边界处理：如果输入列表为空，直接返回None
2. 队列作用：仅保存非None的节点，因为只有这些节点才会有子节点需要分配
3. 顺序填充：用指针ptr按列表顺序遍历，每个父节点依次分配左、右子节点位置：
   • 若当前列表元素为None，则跳过该子节点的创建，直接移动指针
   • 若元素非None，创建节点并关联到父节点，同时将该节点加入队列，等待分配它的子节点

测试示例 #

• 输入[3,9,20,None,None,15,7]，构建出的树结构：

  3
     / \
    9  20
      /  \
     15   7
  

• 输入[2,None,3,None,4,None,5,None,6]，构建出的树结构：

  2
       \
        3
         \
          4
           \
            5
             \
              6
  

内容的提问来源于stack exchange，提问作者Soulfire