0

如何将给定的 BST 重建为包含完全相同密钥的 AVL？算法运行时间应该是 O(n) 并且它允许使用 O(n) 额外的空间。有任何想法吗？整个伪代码不是必需的，任何想法或建议将不胜感激！谢谢！

4

1 回答 1

2
  1. 使用合适的遍历方法（O（n）时间）将所有键提取到排序数组（O（n）空间）
  2. 从排序数组（O（n）时间）构建完美平衡的树（同时为所有节点填充 AVL 平衡因子）

我为你自己的研究省略了细节

于 2013-08-28T05:09:53.620 回答