[CareerCup][Google Interview] Merge Two BST - chkkch - 博客园

[CareerCup][Google Interview] Merge Two BST - chkkch - 博客园

You have two BST, you have to merge them into a single BST, inplace and linear time.

http://www.careercup.com/question?id=8255895

 

 

其中，一位仁兄给出了一个非常漂亮的解答：

we could do it in O(m+n) (m, n sizes of both bsts)
1) Covert Tree1 in to circular doubly linked list. O(m)
Search for "tree list recursion problem" for more details.
2) Convert Tree2 in to circular doubly linked list O(n).
3) Merge Tree1, Tree2 O(m+n)
4) Convert the merged circular doubly linked list to Tree. O(m+n) (Middle node can be chosen as root to make tree balanced).

其中doubly link list，tree node的left和right正好作为链表的前后链接。

当然，要写好每一步其实也不容易的。

1）如何把tree转换为doubly link list

2) 如何merge两个list

3) 如何把doubly link list转换为tree

Read full article from [CareerCup][Google Interview] Merge Two BST - chkkch - 博客园