数组转化成二叉树不考察太复杂

算法思路

将层序遍历序列还原为二叉树（LeetCode 常用输入格式）：下标 i 的左子为 2i+1，右子为 2i+2；null / None / nil 表示空节点，不建子树。

BFS 建树：

1. 根为 arr[0]，空数组或根为空则返回 null
2. 用队列保存「已创建、待挂子节点」的节点
3. 按层序依次取两个元素，分别作为队首节点的左、右子（非空则入队）

示例：[1, 2, 3, null, null, 4, 5] →

    1
   / \
  2   3
     / \
    4   5

时间 O(n)，空间 O(n)（队列与结果树）。

python

from collections import deque
from typing import Any, List, Optional


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


def array_to_tree(arr: List[Any]) -> Optional[TreeNode]:
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i < len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i += 1
    return root

js

function TreeNode(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function arrayToTree(arr) {
    if (!arr.length || arr[0] == null) return null;
    const root = new TreeNode(arr[0]);
    const q = [root];
    let i = 1;
    while (q.length && i < arr.length) {
        const node = q.shift();
        if (i < arr.length && arr[i] != null) {
            node.left = new TreeNode(arr[i]);
            q.push(node.left);
        }
        i++;
        if (i < arr.length && arr[i] != null) {
            node.right = new TreeNode(arr[i]);
            q.push(node.right);
        }
        i++;
    }
    return root;
}

go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// arr 元素为 *int：nil 表示空节点
func arrayToTree(arr []*int) *TreeNode {
    if len(arr) == 0 || arr[0] == nil {
        return nil
    }
    root := &TreeNode{Val: *arr[0]}
    q := []*TreeNode{root}
    i := 1
    for len(q) > 0 && i < len(arr) {
        node := q[0]
        q = q[1:]
        if i < len(arr) && arr[i] != nil {
            node.Left = &TreeNode{Val: *arr[i]}
            q = append(q, node.Left)
        }
        i++
        if i < len(arr) && arr[i] != nil {
            node.Right = &TreeNode{Val: *arr[i]}
            q = append(q, node.Right)
        }
        i++
    }
    return root
}