这道题事实上就是考察树的分层遍历，因为complete binary tree就是按照每一层依次插入元素。这道题也是类似的，我们一直用vector动态地维护倒数第二层节点，这是所有处在还没有满层节点的父节点。我们还维护一个坐标表示当前层最左边的子节点还没有满的节点，随着我们插入，这个坐标一直右移，直到所有节点都有两个子节点了，我们移动到下层继续这个步骤。插入的时间复杂度平摊之后仍然是O(1)，因为我们对这一层所有的节点只遍历两次，一次在维护指正每次右移的时候，一次这层满了更新成下一层所有节点的时候。代码如下:
No comments:
Post a Comment