: 推 jennya: 1.阵列建二元树：(X) 不必使用BFS，使用for循环将阵列跑一 04/07 01:55
: → jennya: 遍就可以做到，省下bfs queue的空间 04/07 01:55
: 推 Ninja5566: 楼上第一题怎么用for 建complete b-tree?我还真想不到 04/07 02:04
: → Ninja5566: 而且还是在不用额外内存的情况下 04/07 02:04
: 推 Ninja5566: 利用pre or inorder traversal建还是需要暂存parent 04/07 02:07
: → Ninja5566: 不然要怎么返回parent node? 04/07 02:07
: 推 jennya: @Ninja5566 你说的对。我原本的想法像是这样： 04/07 02:44
: → jennya: https://www.paste.org/97946 04/07 02:44
: → jennya: 但是仔细一想这的确和BFS差不多。这部分我的确是呛原PO呛 04/07 02:44
: → jennya: 错了。谢谢~~ 04/07 02:44
忍不住认真一下…
其实这是可行的，所以jennya大并没有呛错（疑？）
这就这很像帮array-based tree写一个iterator
顺手写了一下code，没有仔细改，可能不是很concise
https://pastebin.com/AidafGZP
这其实是在工作中可能会出现，很实际的需求：
你在开发一个micro-controller程式，这个环境没有heap，只有超小的stack
memory中已存在一个以array表示的binary search tree
请写一个function在O(N)时间及O(1)空间做完in-order traversal
(N=number of elements)
Notes:
* O(1)空间表示严格来说不能用recursion，否则是O(log(N))
* 我的算法走访每个edge两次，所以是时间O(N)
* 以array表示binary tree是很实继的做法，尤其当资料是immutable时
比为了每个node分别在heap配置空间节省很多