关于递归实现线段树的问题

来源：9-3 创建线段树

ChArLiE_Mills

2019-09-16

老师你说平衡二叉树的右孩子分配到的数据比左孩子多，但是如果输入一个长度为5的数组，那么第一个递归的左孩子不就是从0-2有三个元素，右孩子是3-4两个元素?是我理解错了吗?

写回答

1回答

liuyubobobo

2019-09-17

已采纳

其实对于线段树来说，对于你的例子，左边分配 3 个孩子，右边分配 2 个孩子；还是左边分配 2 个孩子，右边分配 3 个孩子，都是可以的。

具体，你求出 mid = 2，左边是 [left, mid]，右边是 [mid + 1, right]，或者左边是 [left, mid - 1]，右边是 [mid, right]，都是可以的。

继续加油！：）

ChArLiE_Mills

原来如此，谢谢老师！

2019-09-17

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 2

回答 1

回答 1

回答 3