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