s*i 发帖数: 388 | 1 how to convert a binary tree to binary search tree.
what is the complexity?
can you do it in place?
in place = no extra space |
s*i 发帖数: 388 | 2 怕被 w帝 恐吓,偶怕怕,偶就不说偶的解法了,大家随便聊聊idea。
【在 s*i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how to convert a binary tree to binary search tree. : what is the complexity? : can you do it in place? : in place = no extra space
|
g*********s 发帖数: 1782 | 3 what does "in place" mean here?
【在 s*i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怕被 w帝 恐吓,偶怕怕,偶就不说偶的解法了,大家随便聊聊idea。
|
s*i 发帖数: 388 | 4 no extra space
【在 g*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : what does "in place" mean here?
|
f***g 发帖数: 214 | 5 0.02
如果不是inplace,就找个数组临时存一下。
要排序,所以O(nlogn)
如果是inplace,就先变成linked list
排序,再变回来。O(n^2)
复杂度都不低,楼主要不咱私下讨论讨论? |
s*i 发帖数: 388 | 6 好,最近风声紧,咱下来聊。哎,莫谈国事
【在 f***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0.02 : 如果不是inplace,就找个数组临时存一下。 : 要排序,所以O(nlogn) : 如果是inplace,就先变成linked list : 排序,再变回来。O(n^2) : 复杂度都不低,楼主要不咱私下讨论讨论?
|
f*****w 发帖数: 2602 | |
c*******o 发帖数: 1357 | 8 !你就是那个发人肉贴的老衲吗?!
【在 s*i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how to convert a binary tree to binary search tree. : what is the complexity? : can you do it in place? : in place = no extra space
|
s*i 发帖数: 388 | 9 啥?
【在 c*******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : !你就是那个发人肉贴的老衲吗?!
|
a******7 发帖数: 106 | 10 poster-order walk on binary tree, take each node and insert into new binary
search tree, with only pointer manipulation, time complexity O(nlogn) |
|
|
c*******o 发帖数: 1357 | 11 把wolver人肉出来的那个推理贴
作者就自称老衲……
【在 s*i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啥?
|
g*********s 发帖数: 1782 | 12
怎么变回来?
【在 f***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0.02 : 如果不是inplace,就找个数组临时存一下。 : 要排序,所以O(nlogn) : 如果是inplace,就先变成linked list : 排序,再变回来。O(n^2) : 复杂度都不低,楼主要不咱私下讨论讨论?
|
A**y 发帖数: 62 | 13 按in-order遍历树排序?
【在 g*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 怎么变回来?
|
S********t 发帖数: 3431 | 14
google: dsw
【在 s*i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how to convert a binary tree to binary search tree. : what is the complexity? : can you do it in place? : in place = no extra space
|
f***g 发帖数: 214 | 15 上面说了:DSW
【在 A**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 按in-order遍历树排序?
|
t****o 发帖数: 31 | 16 变成排好序的linked list就不用变回去了吧,直接就是退化了的bst啊
【在 f***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0.02 : 如果不是inplace,就找个数组临时存一下。 : 要排序,所以O(nlogn) : 如果是inplace,就先变成linked list : 排序,再变回来。O(n^2) : 复杂度都不低,楼主要不咱私下讨论讨论?
|
f***g 发帖数: 214 | 17 赞,就是不知道算不算in-place
比如说你有一个vector (STL),每次你都取出一个,放到一个新的vector里面去,总共
占用空间没变,可是算不算in-place呢?
binary
【在 a******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : poster-order walk on binary tree, take each node and insert into new binary : search tree, with only pointer manipulation, time complexity O(nlogn)
|
f***g 发帖数: 214 | 18 理论上没错,估计面试官不答应
【在 t****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 变成排好序的linked list就不用变回去了吧,直接就是退化了的bst啊
|
d**f 发帖数: 264 | 19 recursion.
然后再翻转,一共是六种情况
(1-2-3) (3-2-1)
(3-1-2) (2-1-3)
(1-3-2) (2-3-1)
但是需要一个临时的Node空间
如果先转化成doubled linked list.排序能做到O(n^2)吗? |
f***g 发帖数: 214 | 20 有问题。
对于每一个node,你只考虑了它本身和他的两个子node
再往下的不管了?
道理类似于经典题目,判断一个树是不是bst,总是要带着参数递归的。
比如
7
3 9
2 4 8 10
11
你怎么把11转到7的右树去?
如果先转化成doubled linked list.排序能做到O(n^2)吗?
最耗费时间的就是linked list排序O(n2)
其他的都在O(n)解决
【在 d**f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : recursion. : 然后再翻转,一共是六种情况 : (1-2-3) (3-2-1) : (3-1-2) (2-1-3) : (1-3-2) (2-3-1) : 但是需要一个临时的Node空间 : 如果先转化成doubled linked list.排序能做到O(n^2)吗?
|
d**f 发帖数: 264 | 21 我搞错了
【在 f***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有问题。 : 对于每一个node,你只考虑了它本身和他的两个子node : 再往下的不管了? : 道理类似于经典题目,判断一个树是不是bst,总是要带着参数递归的。 : 比如 : 7 : 3 9 : 2 4 8 10 : 11 : 你怎么把11转到7的右树去?
|
s*i 发帖数: 388 | 22 我人肉水平没那么高,也没那么无聊。
【在 c*******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把wolver人肉出来的那个推理贴 : 作者就自称老衲……
|