将排序数组编码为 bst

Question

我使用这种方法将数组转换为二叉搜索树，我得到根节点，其中包含有关树的所有信息。 但我想要它的格式

• 索引 i 处的节点的左子节点位于索引 2i + 1 处
• 右子节点位于索引 2i + 2
• 索引 i 处的节点的父节点位于 索引 [i−1]/2

基本上输出 [16, 10, 24, 7, 12, 20, 28, 4, 8, 11]。

因为这个输出满足

• 父节点 i =0 16
• 左 2*0+1 = 1 (10)
• 右 2*0+2 = 24 所以 16>10 && 16<24

所以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);

Answer 1

看看您想要的输出，看起来您想要构建一个完整的二叉树，这只是二叉搜索树对于给定值可能具有的可能形状之一。此形状不一定将“中间”值放在根部，因此这不是您可以在此处应用的逻辑。

但是，您可以根据输入中值的索引应用一种逻辑。该索引的位模式（以二进制表示法）可用于找出该值应放置在所需（完整）二叉树中的位置。

这是确定在目标树中行走的“路径”的代码，以最终将当前值放入该树中：

function createBinaryTree(nums) {
    const n = nums.length;
    let levels = 1 + Math.floor(Math.log2(n));
    const bottom = n - (1 << (levels - 1)) + 1; // Number of nodes in bottom level
    const tree = [];
    let diff = 0;
    for (let i = 0; i < n; i++) {
        // Here is the magic formula:
        const bits = (i - diff).toString(2).padStart(levels, "0").replace(/01*$/, "");
        // Walk down the tree to the location of where nums[i] should end up
        let j = 0; // Root
        for (let digit of bits) {
            j = j*2 + 1 + +digit; // Go left or right
        }
        // ... and place it there
        tree[j] = nums[i];
        if (j === n - 1) { // This was the last node in the bottom level
            levels--;  // Height of "rest" of the tree is one less
            diff = bottom; // Continue as if there never was this bottom level
        }
    }
    return tree;
}

// Example run:
const nums = [4, 7, 8, 10, 11, 12, 16, 20, 24, 28];
const tree = createBinaryTree(nums);
console.log(...tree);