为什么结果中有11个null而不是10个null

Question

如图中所示，在构建例程中的线段树时，我在最后只画了10个NULL，而程序运行了11个NULL，请问我画的错在那里？

Answer 1

liuyubobobo 2018-06-12 15:58:19

按照你的画法，每个叶子节点左右都是NULL，不管叶子节点有几个，最后肯定有偶数个NULL。我不确定你在程序中是如何验证的？看看是否是程序有问题？

你的根节点区间是[0...5]，一共包含6个元素（0，1，2，3，4，5），最后每个叶子节点都包含一个元素，你又计算每个叶子元素有左右两个NULL，最终应该有12个NULL。看看是你得到的11是最后一个NULL的索引？（从0开始算，索引11对应第12个元素）

课程的所有代码都可以直接在课程的官方github中找到，可以尝试运行课程的官方github代码，看是否有同样的问题？传送门：https://github.com/liuyubobobo/Play-with-Data-Structures

加油！

• 提问者 yushou #1

  老师，课程的代码最后也是11个NULL（总共13个NULL）。但是输出应该只有12个NULL。

• 提问者 yushou #2

  老师因为创建线段树的时候用了大约为2^n(其实是2^n-1)，就使得线段树数组长了一位，值为null, 最后输出的时候多输出了一个null.

• 提问者 yushou #3

  将 tree = (E[])new Object[4 * arr.length]; 改为 tree = (E[])new Object[4 * arr.length - 1];即可正确输出。

点开查看后面3条评论