我正在编写代码，通过先序遍历检查它是否是有效的二叉搜索树。例如，先序遍历1,2,4,3,5是有效的BST，而1,3,4,2不是。
我从先序遍历序列构建整个树，然后检查该树是否是有效的BST。这是一个时间和空间复杂度均为O(N)的解决方案。
有人有比这更好的方法吗？我有一种直觉，认为我们可以在O(1)的额外空间内完成。
检查给定的先序遍历是否是有效的二叉搜索树
12
- Vallabh Patade
3
2如何仅通过先序遍历唯一地构造一棵树？ - P0W
1我有直觉，我们可以在O(1)的额外空间内完成这个任务。为什么呢？ - David Eisenstat
我的解决方案使用O(1)空间 - https://dev59.com/9V8e5IYBdhLWcg3wCGq_#63698918 - Saurav Sahu
10个回答
15
检查1..n的排列是否是一个有效BST的前序遍历（如果存在BST，那么它是唯一的；imreal的答案不是反例，因为第二个重构没有排序）等价于测试该排列是否可以通过堆栈排序，即避免231模式。我似乎找不到任何线性时间常量空间算法在这些名称下，这可能表明鉴于此问题所吸引的关注量，没有人知道一个常量额外空间解决方案。
如果您愿意假设可读/写的输入可以被破坏，则存在一种使用恒定额外空间的线性时间算法。没必要单独重构树然后测试它。以下是相关的Python代码。
def isbstpreorder(iterable):
lowerbound = None
stack = []
for x in iterable:
if lowerbound is not None and x < lowerbound: return False
while stack and stack[-1] < x: lowerbound = stack.pop()
stack.append(x)
return True
为了消除堆栈的单独存储，将其存储在输入列表的前缀中。
- David Eisenstat
2
@David Eisenstat：栈可排序的条件是否足以使前序遍历序列在BST中有效？ - Prashant Bhanarkar
1@Prashant 先序遍历看起来像是<根><左子树的先序遍历><右子树>。必要性通过案例分析得出：根节点不可能涉及假设违规，因为所有小于根节点的元素都在所有大于根节点的元素之前；由于相同的逻辑，2不能属于左子树，而1属于右子树；因此，假设违规局限于一个子树中，并且我们使用归纳假设来处理这种情况。充分性是类似的证明；使用2作为根节点的231条件来显示左子树出现在右子树之前；归纳。 - David Eisenstat
1
这个想法是检查输入数组是否可以分成两个子数组，代表左子树和右子树。显然，这必须递归地完成。
以下是一些经过测试的Java代码，以说明相同的内容：
import java.util.ArrayList;
import java.util.List;
public class PreOrderBSTCheck {
/**
* @param args
*/
public static void main(String[] args) {
String ipStr = "1 4 2 3";
String[] ipArr = ipStr.split(" ");
int[] intArr = new int[ipArr.length];
List<Integer> listArr = new ArrayList<Integer>();
for(int i = 0 ; i < ipArr.length ; i++)
{
intArr[i] = Integer.parseInt(ipArr[i]);
listArr.add(intArr[i]);
}
//System.out.println("List size: "+listArr.size());
if(checkTree(listArr))
System.out.println("Valid");
else
System.out.println("Invalid");
}
public static boolean checkTree(List<Integer> arr)
{
if(arr.size() == 1)
{
return true;
}
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
Integer root = arr.get(0);
int idx = 1;
//adding left subtree nodes
while(arr.get(idx) < root)
{
left.add(arr.get(idx++));
if(idx >= arr.size())
break;
}
//adding right subtree nodes
if(! (idx >= arr.size()))
while(arr.get(idx) > root)
{
right.add(arr.get(idx++));
if(idx >= arr.size())
break;
}
if(left.size() + right.size() == arr.size() - 1)
{
if(left.size()==0)
{
return true && checkTree(right);
}
else if(right.size() == 0)
{
return true && checkTree(left);
}
else
{
return checkTree(left) && checkTree(right);
}
}
else
{
return false;
}
}
}
- Vikas Tikoo
1
你可以避免在每个递归中为每个子树创建列表。这是不必要的空间开销，可以通过传递原始列表的索引来简单地避免。 - Saurav Sahu
1
isBST(vector<int> &A) {
int a=0,b=1,c=2;
if(A.size() <= 2)
return 1;
while(c < A.size())
{
if(A[a] < A[b] && A[b] > A[c] && A[c] < A[a])
return 0;
a++; b++; c++;
}
return 1;
}
8
7 9 output preorder 8 7 9
7
8
9 output preorder 7 8 9
7
9
8 output preorder 7 9 8
9
7
8 output preorder 9 7 8
9
8
7 out put preorder 9 8 7
但是对于897，构建二叉搜索树是不可能的。
- Ramandeep Singh
1
针对 {2, 4, 3} 这种情况，我们可以构建一棵二叉搜索树，但是您的解决方案会返回 0。 - Himanshu Singh
0
int lower=-1;
for(long int i=0;i<size;i++)
{
if(lower>-1 && pre[i] < lower)
{
lower=-2;
break;
}
while(!isempty(s) && top(s)<pre[i])
{
lower =top(s);
pop(s);
}
push(s,pre[i]);
}
if(lower==-2)
{
cout<<"Invalid"<<endl;
}
else
{
cout<<"Valid BST"<<endl;
}
这个算法适用于任何类型的排序输入，而不仅仅是1到n。它只需要O(1)的额外空间，即只有变量“lower”。如果您尝试使用笔和纸解决此问题，您将不得不跟踪一个变量，即用于检查任何新出现的值都不应小于该值的变量。Lower充当该标记，以便您检查没有新值低于'lower'。并且一旦您获得更高的值，就会立即更新'lower'。
- Romil Punetha
0
在这里，我们可以考虑的第一件事是对于前序遍历数组，如果在数组右侧的任何点上找到比当前元素更大的元素，并且在此之后的任何元素都是较小的元素，则应该考虑从给定的前序遍历中不可能构建BST。
例如：arr[] = {40,30,35,20,80,100} 无法构建有效的BST。
解释：
在这里，当我们开始构建树时，40成为BST的根，现在随着我们的继续，30进入左子树，现在我们找到了30的下一个更大的数，即35，因为我们知道任何低于或小于30的元素都必须在30和其下一个更大的元素之间，即35。因此，当我们向前遍历时，我们发现20不能适合30的左侧，因为它在下一个更大的元素之后，肯定不是35的子节点，因为它将违反BST属性（即任何右子树元素始终比根具有更大的值）。因此，无法构建有效的BST。
现在，为了解决这个问题，我们可以使用栈，就像我们在数组中查找下一个更大的元素一样下一个更大元素的代码。在这里，我们只需要确保在找到下一个更大的元素后，没有比它更小的元素出现。
在代码中，我们最初将根节点设置为INT_MIN，即可能的最低值， 如果根节点任何时候都比当前元素低，我们返回false。 当当前元素大于栈顶元素时，我们弹出栈顶元素并将根节点设置为弹出的元素。 然后我们将当前元素推入栈中进行进一步比较。
bool check(int *arr, int n)
{
stack<int> s;
int root=INT_MIN;
for(int i=0;i<n;++i)
{
if(arr[i]<root)
return false;
while(!s.empty() && arr[i]>s.top())
{
root=s.top();
s.pop();
}
s.push(arr[i]);
}
return true;
}
- Prashant Shubham
0
public static bool IsBST(List<int> array)
{
var s = new Stack<int>();
int root = 0;
foreach(var el in array)
{
if(el < root)
return false;
while(s.Count != 0 && el > s.Peek())
{
root = s.Peek();
s.Pop();
}
s.Push(el);
}
return true;
}
- Cata Hotea
0
不使用额外的空间或容器（如stack）：
将输入数组分成这种形式[root] - [left-subtree] - [right-subtree]，然后递归验证每个子树。
public boolean isValidPreorder(int[] A) {
return util(A, 0, A.length-1);
}
public boolean isValidPreorderUtil(int[] A, int x, int y){
if (x >= y) return true;
for (int i = x+1; i <= y; i++){
if (A[x] < A[i]) {
for (int k = i+1; k <=y; k++){
if (A[k] < A[x]) return 0;
}
return util(A, x+1, i-1) & util(A, i, y); // both left and right subtree
}
}
return util(A, x+1, y); // left subtree only
}
- Saurav Sahu
1
3这个解决方案不是无栈的，隐式地使用了调用栈，平均情况下的空间复杂度为O(h)，最坏情况下为O(n)。此外，时间复杂度为O(n^2)。 - Pranshu
0
这个问题与从先序遍历构造二叉搜索树类似。
我在C++中的解决方案是：
在这里，函数solve接受一个名为preorder的向量A。我使用了集合来检查不同的条目，并维护了一个minVal变量，它有效地作为堆栈的替代品。因此，我的解决方案需要O(1)的额外空间，并且具有O(n)的时间复杂度。
我在C++中的解决方案是：
int Solution::solve(vector<int> &A) {
set<int> s;
for(auto&I: A)
s.insert(I);
if(s.size() != A.size())
return 0;
int minVal = INT_MIN;
for(int i = 0; i < A.size(); i++){
if(A[i] <= minVal)
return 0;
if(i > 0 && A[i] > A[i-1])
minVal = A[i-1];
}
return 1;
}
在这里，函数solve接受一个名为preorder的向量A。我使用了集合来检查不同的条目，并维护了一个minVal变量，它有效地作为堆栈的替代品。因此，我的解决方案需要O(1)的额外空间，并且具有O(n)的时间复杂度。
- Jaideep
-1
这可以在O(n)时间和O(n)辅助空间复杂度（递归栈）内完成。整个树的根节点将位于前序数组的索引0处。在前序遍历中，每个节点后面都是其左子树元素的集合，然后是右子树元素的集合。对于每个节点，右子树将以该节点的下一个更高的数组值为根。因此，基本思想是递归地将前序数组划分为具有节点值有效范围的左右子树。
public class IsBstPossibleFromPreorder {
public static void main(String args[]){
int[] preorder = {40, 30, 35, 20, 80};//{6,3,0,5,4,8,7,9};//{3,2,5,1,7};
System.out.println(isBstPossible(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, preorder.length-1));
}
/*
li is root of current subtree
ri is the index of the last element in the current subtree
min, max range for the elements of current subtree
*/
private static boolean isBstPossible(int[] preorder, int min, int max, int li, int ri){
if (li==ri && preorder[li]>min && preorder[li]<max){ // if single node subtree...
return true;
}
if (preorder[li]<=min || preorder[li]>=max ){ // if node value out of range
return false;
}
int lsi = preorder[li+1]<preorder[li]?li+1:-1; // left subtree root index (-1 if no left subtree exits for node li)
int rsi = findNextHigherElementIndex(preorder, li, ri); // right subtree root index (-1 if no right subtree exists for node li)
boolean isLeftValid = (lsi==-1 || isBstPossible(preorder, min, preorder[li], lsi, rsi-1>lsi?rsi-1:lsi));
boolean isRightValid = (rsi==-1 || isBstPossible(preorder, preorder[li], max, rsi, ri));
return isLeftValid && isRightValid;
}
private static int findNextHigherElementIndex(int[] preorder, int li, int ri){
int x = -1; // -1 if no higher element on right side of li
for (int i = li+1; i <= ri ; i++) {
if (preorder[i]>preorder[li]){
x = i;
break;
}
}
return x;
}
}
- Aditya Joshee
-3
仅凭先序遍历无法唯一构建二叉树，因此无法验证它是否为BST。
例如，4、2、3、6、5可以构成:
4
/ \
2 6
\ /
3 5
这是一棵二叉搜索树，同时也是：
4
\
2
\
3
\
6
\
5
这不是。
- imreal
9
8第二个不是二叉搜索树。 - Vallabh Patade
@DavidEisenstat 两棵树产生相同的前序遍历序列，但它们显然是不同的树。 - imreal
2@imreal 我们在谈论二叉搜索树。 - Vallabh Patade
1@imreal 我认为OP所问的只是如何展示一个给定的前序遍历序列可以与BST相关联。而你所展示的是，一个可以与BST相关联的前序遍历序列也可以与某些不是BST的东西相关联。但这并不是问题所在。问题是要确定何时一个给定的序列根本无法与BST相关联。 - John Thompson
1第二棵树不是BST。 - PunK _l_ RuLz
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接