检查给定的预先遍历是否有效BST

Question

我正在编写代码来检查从预先遍历如果它是一个有效的BST。 例如，前序遍历1,2,4,3,5是有效的BST，而1,3,4,2不是

我从该预序列构建整棵树，然后检查该树是否是有效的BST。这是关于空间和时间复杂性的解决方案。

有没有人比这更好的方法？我有直觉，我们可以在O（1）额外的空间中做到这一点。

Answer 1

检查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 

要消除堆栈的单独存储，请将其存储在输入列表的前缀中。

Answer 2

从单独的前序遍历中不可能唯一地构造二叉树，所以不可能验证它是否是BST。

例如，4，2，3，6，5可以使：

4 
/ \ 
2  6 
    \ /
    3 5 

其是BST和也：

4 
\ 
    2 
    \ 
    3 
    \ 
     6 
     \ 
     5 

这是不。

Answer 3

这个想法是检查输入数组是否可以分成两个子数组，代表左边和右边的子树。显然，这必须递归地完成。

下面是一些测试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; 
     } 

    } 

} 

Answer 4

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'。如果您尝试使用笔和纸来解决此问题，则必须跟踪一个变量，该变量是您检查没有新发生的值应小于此值的变量。较低的行为作为您检查没有新值低于'低'的标记。只要你获得更高的价值，你就会不断更新'更低'。

Answer 5

这可以在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; 
    } 
} 

Answer 6

我们可以认为这里的前序遍历数组，如果在阵列上的右侧任意一点上，我们比当前元素得到更大的元素，如果之后的任何元素为更小的元素，我们应该考虑的第一件事情BST不可能从给出的那种非常先序的遍历中得到。

例如：arr [] = {40,30,35,20,80,100}无法构建有效的BST。

说明：

这里的时候，我们开始建立树40成为BST的根， 现在，当我们继续30进入左子树，现在我们发现的30是35下更大，因为我们知道对于任何在30左子树中的较小或较小的元素，应该在30和它的下一个更大的即35之间。所以，当我们向前走时，我们发现20个不能放在30的左边，因为它位于下一个更大的元素之后，当然不会像35的子元素那样违反BST属性（即任何右子树元素必须具有更大的值总是与根相比）。因此，无法制作有效的BST。

现在，为了解决这个问题，我们可以使用堆栈，因为我们使用它来查找数组中的下一个更大元素Code for next greater element。在这里，我们必须确保在下一个更大的元素之后没有元素小于之后的元素。

在代码中，我们最初将根作为INT_MIN尽可能最小的值， 如果根在任何时候低于当前元素，我们将返回false。 当前元素大于堆栈顶部的元素时，我们弹出它并将root设置为弹出元素。 然后我们将当前元素推入堆栈以进行进一步比较。

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; 
}