Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
9 lines (6 sloc) 580 Bytes

这个题目要我们借用上面两个习题的结果,来构造O(n)时间复杂度的union-setintersection-set操作。

习题2.63中的tree->list-2的时间复杂度为O(n),用有序列表的实现的union-setintersection-set时间复杂度也是O(n),然后习题2.64中的list->tree的时间复杂度也是O(n)

分析到这里,这个题目就很明显了:

  1. 调用tree->list-2把树转为有序列表
  2. 调用有序列表的union-setintersection-set方法
  3. 调用list-tree把上面两个方法的结果再转为平衡树