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 的大作中提到】
: 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 的大作中提到】
: 怕被 w帝 恐吓，偶怕怕，偶就不说偶的解法了，大家随便聊聊idea。
|
s*i
发帖数: 388 | 4 no extra space
【在 g*********s 的大作中提到】
: 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 的大作中提到】
: 0.02
: 如果不是inplace，就找个数组临时存一下。
: 要排序，所以O(nlogn)
: 如果是inplace，就先变成linked list
: 排序，再变回来。O(n^2)
: 复杂度都不低，楼主要不咱私下讨论讨论？
|
f*****w
发帖数: 2602 | |
c*******o
发帖数: 1357 | 8 !你就是那个发人肉贴的老衲吗？！
【在 s*i 的大作中提到】
: 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 的大作中提到】
: !你就是那个发人肉贴的老衲吗？！
|
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 的大作中提到】
: 啥？
|
g*********s
发帖数: 1782 | 12
怎么变回来？
【在 f***g 的大作中提到】
: 0.02
: 如果不是inplace，就找个数组临时存一下。
: 要排序，所以O(nlogn)
: 如果是inplace，就先变成linked list
: 排序，再变回来。O(n^2)
: 复杂度都不低，楼主要不咱私下讨论讨论？
|
A**y
发帖数: 62 | 13 按in-order遍历树排序？
【在 g*********s 的大作中提到】
:
: 怎么变回来？
|
S********t
发帖数: 3431 | 14
google: dsw
【在 s*i 的大作中提到】
: 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 的大作中提到】
: 按in-order遍历树排序？
|
t****o
发帖数: 31 | 16 变成排好序的linked list就不用变回去了吧，直接就是退化了的bst啊
【在 f***g 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 变成排好序的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 的大作中提到】
: 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 的大作中提到】
: 有问题。
: 对于每一个node，你只考虑了它本身和他的两个子node
: 再往下的不管了？
: 道理类似于经典题目，判断一个树是不是bst，总是要带着参数递归的。
: 比如
: 7
: 3 9
: 2 4 8 10
: 11
: 你怎么把11转到7的右树去？
|
s*i
发帖数: 388 | 22 我人肉水平没那么高，也没那么无聊。
【在 c*******o 的大作中提到】
: 把wolver人肉出来的那个推理贴
: 作者就自称老衲……
|
