1回答

liuyubobobo

2021-05-11

已采纳

关键是由于我们使用数组表示这棵二叉树，所以，这棵二叉树必须是完全二叉树。最后一层没有元素的地方会浪费空间。

以 6 个节点为例（1， 2， 3， 4， 5，6）。得到的二叉树是这个样子的。

            O
       /        \
     O            O
   /   \        /   \
  O     3      O     6
 / \   / \    / \
1   2 X   X  4   5

​

注意两个 X 的地方，他们是占空间的，虽然我们的算法不会访问这里，但是，为了访问 4, 5 两个节点，X 所在的空间只能浪费。因此，这棵有 6 个叶子节点的树，使用 12 个节点是不够的。

==========

但这里要说明的是，因为这个代码使用了递归的方式，自顶向下构造这棵树，所以在这里会产生根节点的左右子树分别覆盖三个节点的情况。

如果是自底向上构造，可以避免这个空间的耗费。 此时，使用 2n 的空间就够了。（类似于归并排序自底向上构造）。

自底向上构造平衡树的方式课程中没有介绍，如果感兴趣可以自己实现一下，是一个很好的练习：）

继续加油！：）

0

hiuyubobobo

回复

hiaobai00000

hp>赞！完全正确：）

h021-05-12

共2条回复