Front

事情是这样的，最近面字节的是时分，面试官让我实现一个满二叉树。

先说一下什么是满二叉树，就是每增加一个节点都从左到右放入，比如我顺次增加[1,2,3,4,5],那么就会构成下面的一颗满二叉树。

我这样实现满二叉树，字节面试官都无语了

思路

我的思路是经过一个数组去保护所以增加的node,这个数组就叫nodeList吧。由于每个二叉树的节点都只有两个左和右，我会用一个下标index来记载当前需求增加子节点的node,然后让每个node发生引用联系，最终返回nodeList第一个节点就是我们需求的那颗完好的满二叉树。


class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class FullTree {
    constructor() {
        console.log('init')
    }
    nodeList = []
    index = 0
    insertNode = (value) => {
        if (this.nodeList.length === 0) {
            this.nodeList.push(new Node(value))
        } else {
            let { left, right } = this.nodeList[this.index]
            this.nodeList.push(new Node(value))
            if (!left) return this.nodeList[this.index].left = this.nodeList[this.nodeList.length - 1]
            if (!right) {
                this.nodeList[this.index].right = this.nodeList[this.nodeList.length-1]
                this.index += 1
            }
        }
    }
    root = () => this.nodeList[0]
}
let tree = new FullTree()
tree.insertNode(1)
tree.insertNode(2)
tree.insertNode(3)
tree.insertNode(4)
tree.insertNode(5)
console.log(tree.root())

我这样实现满二叉树，字节面试官都无语了

用数组保护二叉树的好处了是，我可以很轻松的找到“它的最大或许最小节点，也可以很轻松的删去指定的某节点”，这也是当时面试官还提的两个要求，这儿就不写了，有爱好的同学自己去思考一下。

End

如果你有其他实现的方案，可以写在评论区中，show me your code !!!

我这样实现满二叉树，字节面试官都无语了