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 !!!