将有序数组转换为二叉搜索树并输出为指定数组存储格式

问题需求 #

已有将有序数组转换为平衡二叉搜索树（BST）的实现，得到TreeNode根节点。现在需要将该BST转换为符合以下索引规则的数组格式：

• 索引i的节点的左子节点位于索引2i+1处
• 索引i的节点的右子节点位于索引2i+2处
• 索引i的节点的父节点位于索引[(i-1)/2]（向下取整）处

期望输出示例：[16, 10, 24, 7, 12, 20, 28, 4, 8, 11]，该数组满足BST属性，且完全符合上述索引规则。

现有代码 #

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var sortedArrayToBST = function(nums) {
    return createBinary(nums, 0, nums.length-1);
}

function createBinary(nums, start, end) {
    if (start > end) {
        return null;
    }
    const mid = Math.floor((start + end) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = createBinary(nums, start, mid - 1);
    root.right = createBinary(nums, mid + 1, end);
    return root;
}

nums = [4, 7, 8, 10, 11, 12, 16, 20, 24, 28];
const root = sortedArrayToBST(nums);
console.log(root);

解决方案 #

要实现TreeNode到目标数组的转换，可使用广度优先搜索（BFS，层序遍历），因为目标数组的索引规则对应完全二叉树的层序存储结构。具体步骤：

1. 初始化队列，存入根节点及其初始索引0
2. 创建与原数组长度一致的结果数组（平衡BST节点数等于原数组元素数）
3. 遍历队列，取出节点和对应索引，将值存入结果数组；同时将子节点与计算出的对应索引加入队列

完整实现代码 #

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var sortedArrayToBST = function(nums) {
    return createBinary(nums, 0, nums.length-1);
}

function createBinary(nums, start, end) {
    if (start > end) {
        return null;
    }
    const mid = Math.floor((start + end) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = createBinary(nums, start, mid - 1);
    root.right = createBinary(nums, mid + 1, end);
    return root;
}

// 新增：TreeNode转目标数组的函数
function treeNodeToCompleteArray(root, totalNodes) {
    const result = new Array(totalNodes);
    const queue = [[root, 0]];
    
    while (queue.length > 0) {
        const [node, index] = queue.shift();
        result[index] = node.val;
        
        if (node.left) {
            queue.push([node.left, 2 * index + 1]);
        }
        if (node.right) {
            queue.push([node.right, 2 * index + 2]);
        }
    }
    
    return result;
}

nums = [4, 7, 8, 10, 11, 12, 16, 20, 24, 28];
const root = sortedArrayToBST(nums);
const targetArray = treeNodeToCompleteArray(root, nums.length);
console.log(targetArray); // 输出: [16, 10, 24, 7, 12, 20, 28, 4, 8, 11]

说明 #

• sortedArrayToBST生成的是平衡BST，结构完全匹配完全二叉树形态，无需处理空节点占位，数组长度与原有序数组一致
• 层序遍历通过队列绑定节点与对应索引，确保每个节点值被放入符合规则的数组位置

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