m**********e
发帖数: 52 | 1 Given a list of numbers, determine whether it can represent the pre-order
traversal list of a binary search tree (BST).
这个除了重构二叉树，还有什么好的解法吗？ |
p*****r
发帖数: 1883 | 2 不用重构树，引文满足preorder只可能是left<=root<=right，所以就一路往前走，把
root放到栈里，看接下来三个是不是满足这个条件就行了。如果只剩两个，只可能是
left<=root，如果只剩一个就是root本身。用递归写一下就行了，几行吧。
【在 m**********e 的大作中提到】
: Given a list of numbers, determine whether it can represent the pre-order
: traversal list of a binary search tree (BST).
: 这个除了重构二叉树，还有什么好的解法吗？
|
k****i
发帖数: 128 | 3 有可能有左右子树为空的情况啊
【在 p*****r 的大作中提到】
: 不用重构树，引文满足preorder只可能是left<=root<=right，所以就一路往前走，把
: root放到栈里，看接下来三个是不是满足这个条件就行了。如果只剩两个，只可能是
: left<=root，如果只剩一个就是root本身。用递归写一下就行了，几行吧。
|
l**o
发帖数: 356 | 4 不知道我说的对不对
根为第一个数，一直往前走，碰到第一个比根大的数为右子树的根，继续往前走，如果
碰到比根小的，返回false。再检查他的左右子树是否满足bst |
m**********e
发帖数: 52 | 5 跟我想的一样，但这样递归复杂度是n^2了，还不如重构快了
【在 l**o 的大作中提到】
: 不知道我说的对不对
: 根为第一个数，一直往前走，碰到第一个比根大的数为右子树的根，继续往前走，如果
: 碰到比根小的，返回false。再检查他的左右子树是否满足bst
|
b********0
发帖数: 62 | 6 那样也是nlgn吧
【在 m**********e 的大作中提到】
: 跟我想的一样，但这样递归复杂度是n^2了，还不如重构快了
|
t******i
发帖数: 35 | 7 下面代码好像可以跑过几个case, 就是用两个 minStack, maxStack，在 traverse
list
同时判断是否是valid BST.
bool listValidBSTHelper(stack &minsk, stack &maxsk, list::
iterator &it, list &l) {
if (it == l.end()) return true;
if (minsk.empty() || maxsk.empty()) return false;
if (*it <= minsk.top() || *it >= maxsk.top()) {
int val = maxsk.top();
maxsk.pop();
minsk.push(val);
return listValidBSTHelper(minsk, maxsk, it, l);
}
maxsk.push(*it);
it++;
if (false == listValidBSTHelper(minsk, maxsk, it, l)) return false;
if (false == listValidBSTHelper(minsk, maxsk, it, l)) return false;
return true;
}
bool isListValidBST(list &l) {
list::iterator it = l.begin();
stack minsk, maxsk;
minsk.push(INT_MIN);
maxsk.push(INT_MAX);
return listValidBSTHelper(minsk, maxsk, it, l);
} |
b***e
发帖数: 1419 | 8 There is a simple O(n) algorithm:
var isPreOrder = function(arr) {
var stack = [];
var i = 0;
var largestSoFar;
while(i < arr.length) {
var l = stack.length;
if (l == 0 || arr[i] < stack[l-1]) {
stack.push(arr[i]);
i++;
} else {
var out = stack.pop();
if (largestSoFar == undefined || out >= largestSoFar) {
largestSoFar = out;
} else {
return false;
}
}
}
return true;
};
【在 m**********e 的大作中提到】
: Given a list of numbers, determine whether it can represent the pre-order
: traversal list of a binary search tree (BST).
: 这个除了重构二叉树，还有什么好的解法吗？
|
q****o
发帖数: 6 | 9 想了一下，想明白了。blaze大神好牛
【在 b***e 的大作中提到】
: There is a simple O(n) algorithm:
: var isPreOrder = function(arr) {
: var stack = [];
: var i = 0;
: var largestSoFar;
:
: while(i < arr.length) {
: var l = stack.length;
: if (l == 0 || arr[i] < stack[l-1]) {
: stack.push(arr[i]);
|
z***b
发帖数: 127 | 10 他这个代码是啥意思啊？能详细说下嘛？
【在 q****o 的大作中提到】
: 想了一下，想明白了。blaze大神好牛
|
r****7
发帖数: 2282 | 11 大哥，你能举一个不能represent preorder BST的list么。。。
是不是要balanced？
【在 m**********e 的大作中提到】
: Given a list of numbers, determine whether it can represent the pre-order
: traversal list of a binary search tree (BST).
: 这个除了重构二叉树，还有什么好的解法吗？
|
b********0
发帖数: 62 | 12 我觉得不像O(n)...
【在 b***e 的大作中提到】
: There is a simple O(n) algorithm:
: var isPreOrder = function(arr) {
: var stack = [];
: var i = 0;
: var largestSoFar;
:
: while(i < arr.length) {
: var l = stack.length;
: if (l == 0 || arr[i] < stack[l-1]) {
: stack.push(arr[i]);
|
e*******i
发帖数: 56 | 13 @Blaze. ur code is wrong.
2, 3, 1 can NOT be preorder of a BST. But ur code returns true. |
b***e
发帖数: 1419 | 14 Edge case. Add an infinity to the end of the input array and you'll be all
set. I'll modify the code anyways.
【在 e*******i 的大作中提到】
: @Blaze. ur code is wrong.
: 2, 3, 1 can NOT be preorder of a BST. But ur code returns true.
|
