用O(n)时间和O(n)空间将BST转换为最大堆的主要技术是什么?
我的进展。我在想用inorder traversal的方法,把节点按升序保存在new ArrayList里。但我不知道如何继续?任何帮助都将被强烈感激。
二进制搜索树的无序遍历按排序顺序返回项目。反向无序遍历(即右、节点、左)返回按反向排序的项目。
一个反向排序的列表是一个有效的最大堆。
例如,给定这个二进制搜索树。
5
3 8
1 4 6 9
反向遍历得到的是 [9,8,6,5,4,3,1]
,对应于这个最大堆。
9
8 6
5 4 3 1