JavaScript 从数组构建不完整二叉树

Question

这似乎是一个重复的问题，但我无法在 SOF 或其他地方的任何地方找到我的问题的答案。

我想建立一个 不完全二叉树 来自 数组 和 非空根节点 , 在 JavaScript 与 null值代表null子树，而不是值 = null 的子树.

预期结果:

TreeNode {
  val: 1,
  left:
   TreeNode {
     val: 2,
     left: TreeNode { val: 4, left: null, right: null },
     right: null },
  right:
   TreeNode {
     val: 3,
     left: null,
     right: TreeNode { val: 5, left: null, right: null } } }

上面的预期输出可以像这样手动完成:

const myTree = new TreeNode(1);
myTree.left = new TreeNode(2);
myTree.left.left = new TreeNode(4);
myTree.right = new TreeNode(3);
myTree.right.right = new TreeNode(5);

树应如下所示:

   1
   /\
  2  3
 /    \
4      5

这是我的代码:

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    insert(values, i = 0) {
        if (i >= values.length) return;
        const queue = [this];
        while (queue.length > 0) {
            let current = queue.shift();
            if (current.left === null) {
                current.left = new TreeNode(values[i]);
                break;
            }
            queue.push(current.left);
            if (current.right === null) {
                current.right = new TreeNode(values[i]);
                break;
            }
            queue.push(current.right);
        }
        this.insert(values, i + 1);
        return this;
    }
}
(function() {
    // This builds a tree with null nodes with null values and null children.
    // The goal is to skip updating any null child
    const myTree = new TreeNode(1);
    myTree.insert2([2,3,4,null,null,5]);
    console.log(myTree);
}());

这里的问题是我得到一个 null child 作为具有 value = null 的 TreeNode，如下所示:

TreeNode {
  value: 1,
  left:
   TreeNode {
     value: 2,
     left: TreeNode { value: 4, left: null, right: null },
     right: TreeNode { value: null, left: null, right: null } },
  right:
   TreeNode {
     value: 3,
     left: TreeNode { value: null, left: null, right: null },
     right: TreeNode { value: 5, left: null, right: null } } }

我可以通过添加来处理空节点的子节点:

constructor(value) {
      this.value = value;
      if (value) this.left = null;
      if (value) this.right = null;
    }

但我无法仅添加 null值而不是完整的 TreeNode .
我试过了:

if (current.left === null) {
    current.left = values[i] !== null ? new BinaryTree(values[i]) : null;
    break;
}

或者:

if (current.left === null && values[i]) {}

或者:

if (!values[i]) return;

但是没有返回预期的结果。

我还查看了一些使用 Java 的解决方案，但答案使用 Java 中的内置 LinkedList，所以我不确定这是在 JS 中做的正确方法。

Answer to Scott Sauyet's question:

的预期结果

const myTree = new TreeNode (1); 
myTree .insert ([2,null, 4, null, 6, 7])

是:

TreeNode {
    val: 1,
    left: TreeNode {
        val: 2,
        left: TreeNode {
            val: 4,
            left: TreeNode { val: 6, left: null, right: null },
            right: TreeNode { val: 7, left: null, right: null }
        },
        right: null
    },
    right: null
}

Answer 1

您通过检查 values[i] 做对了对于 null ，而不是在 null 时创建新节点，但您还需要跳过该节点以获取任何后续值。这在递归解决方案中很难做到，所以我建议让它迭代:

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    insert(values) {
        const queue = [this];
        let i = 0;
        while (queue.length > 0) {
            let current = queue.shift();
            for (let side of ["left", "right"]) {
                if (!current[side]) {
                    if (values[i] !== null) {
                        current[side] = new TreeNode(values[i]);
                    }
                    i++;
                    if (i >= values.length) return this;
                }
                if (current[side]) queue.push(current[side]);
            }
        }
        return this;
    }
}

(function() {
    const myTree = new TreeNode(1);
    myTree.insert([2,3,4,null,null,5]);
    console.log(myTree);
}());

但请注意，如果您调用 myTree.insert多次，然后是前一个 null节点将使用新数据进行扩展。

如果这是不希望的，那么您可以采取的一种措施是删除 insert方法，并仅通过构造函数提供此功能。

或者，否则，您首先需要使用排队机制来找出应该扩展的节点。它们是那些没有 2 个子节点的节点，并且没有(按 BFS 顺序)有子节点的节点。

这是看起来的样子(用一个更大的树作为演示):

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    getInsertionPoints() {
        // find uninterrupted series of leaves in BFS order
        const queue = [this];
        const leaves = [];
        while (queue.length) {
            let current = queue.shift();
            for (let side of ["left", "right"]) {
                if (current[side]) {
                    queue.push(current[side]);
                    leaves.length = 0; // reset
                } else {
                    leaves.push([current, side]);
                }
            }
        }
        return leaves;
    }
    insert(values) {
        let queue = this.getInsertionPoints();
        for (let value of values) {
            let [current, side] = queue.shift();
            if (value !== null) {
                current[side] = new TreeNode(value);
                queue.push([current[side], "left"], [current[side], "right"]);
            }
        }
        return this;
    }
}

(function() {
    const myTree = new TreeNode(1);
    myTree .insert ([2,null, 4, null, 6, 7]);
    myTree .insert ([8, null, 9, 10, 11, 12]);
    console.log(myTree);
}());