檢查給定的預先遍歷是否有效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; 
}