我调试过程中发现，课程中线段树的树形图示与实际代码可能不相符
来源：9-7 更多线段树相关的话题
慕粉3458977
2020-05-01
如下图中，最底层叶子节点总是靠右的，而代码跑出来的结果却总是靠左。
以节点A[5…9]为例，mid = 7，从代码来看，左分支节点应该为A[5…7]，右分支节点应该为A[8…9]；
同时，我们不可以把代码改为buildSegmentTree(leftTreeIndex, l, mid - 1);因为mid是可能为0的；
所以我认为，当节点的区间元素数量为奇数时，左子树应该涵盖更大的区间，而右子树偏少，所以整棵树的最底层叶子节点应该是靠左的。
不知道我想的对不对…
private void buildSegmentTree(int treeIndex, int l, int r){
if(l == r){
tree[treeIndex] = data[l];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
// int mid = (l + r) / 2;
int mid = l + (r - l) / 2;
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
写回答
1回答
-
你是的对的。代码中我的 mid 的计算方式实际上是下取整，并且左边包含 mid，所以在奇数的情况下，左边的节点会多。
虽然这个图也是线段树，但确实没有准确反映课程代码对应的线段树。抱歉！
继续加油！：）
032020-05-01
相似问题