LeetCode二叉树数组表示与自定义类差异及转换逻辑问询

你在Udemy学习的是**二叉搜索树（BST）的构建逻辑——通过数值大小比较插入节点，而LeetCode中用数组表示的二叉树是基于层序遍历（广度优先遍历）**的序列化结果，两者的构建规则完全不同，这是核心差异点。

一、LeetCode数组序列化的规则 #

数组按层序遍历的顺序存储二叉树节点：

• 数组第一个元素是二叉树的根节点
• 对于数组中第i个位置的节点（从0开始计数）：
  • 它的左子节点位于2*i + 1的位置
  • 它的右子节点位于2*i + 2的位置
• 若数组对应位置的值为null，表示该位置不存在节点，其对应的子节点位置也无需处理

以你给出的示例root = [3,9,20,null,null,15,7]为例：

1. 索引0：值为3 → 根节点
2. 索引1：值为9 → 根节点的左子节点；索引2：值为20 → 根节点的右子节点
3. 索引3、4为null → 节点9的左右子节点均不存在
4. 索引5：值为15 → 节点20的左子节点（计算：2*2+1=5）；索引6：值为7 → 节点20的右子节点（计算：2*2+2=6）

二、JavaScript实现数组转二叉树 #

使用队列（先进先出）来模拟层序遍历的构建过程，代码如下：

// LeetCode官方TreeNode定义
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

// 数组转二叉树函数
function arrayToBinaryTree(arr) {
    // 空数组或根节点为null时直接返回null
    if (!arr.length || arr[0] === null) return null;

    // 创建根节点并加入队列
    const root = new TreeNode(arr[0]);
    const queue = [root];
    let index = 1;

    // 循环处理队列中的节点，直到数组遍历完成或队列为空
    while (queue.length > 0 && index < arr.length) {
        const currentNode = queue.shift();

        // 处理左子节点
        if (arr[index] !== null) {
            currentNode.left = new TreeNode(arr[index]);
            queue.push(currentNode.left);
        }
        index++;

        // 处理右子节点（需先判断是否还在数组范围内）
        if (index < arr.length && arr[index] !== null) {
            currentNode.right = new TreeNode(arr[index]);
            queue.push(currentNode.right);
        }
        index++;
    }

    return root;
}

// 测试示例
const testArr = [3,9,20,null,null,15,7];
const treeRoot = arrayToBinaryTree(testArr);
console.log(treeRoot);

三、与BST插入逻辑的区别 #

你之前尝试用BST的insert方法来构建LeetCode的二叉树是行不通的：

• BST的插入是根据数值大小决定节点位置（小值放左，大值放右），构建出的是有序二叉树
• LeetCode的数组是任意二叉树的层序快照，节点位置由遍历顺序决定，和数值大小无关

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