檢查給定的數組是否可以表示二進制搜索樹的級別順序遍歷


難度級別 容易獎學金
經常問 亞馬遜 思傑 IBM 確實 信息邊緣 OYO房間 Teradata數據
二進制搜索樹 二叉樹 隊列 樹遍歷

問題陳述

問題“檢查給定的數組是否可以表示二進制搜索樹的層級遍歷”問題表明,您已獲得對層級的遍歷遍歷。 二叉搜索樹。 並使用 級別順序遍歷 的樹。 我們需要有效地查找級別順序遍歷是否可以表示二進制搜索樹?

Level Order Traversal - {5 2 7 1 6 9 }
True

 

檢查給定的數組是否可以表示二進制搜索樹的級別順序遍歷

解釋

給定的級別順序遍歷表示圖像中顯示的二叉樹。 正如我們所看到的,該樹滿足二叉樹的所有屬性,因此輸出為true。

檢查給定數組是否可以表示二叉搜索樹的層級遍歷的方法

天真的方法

如果我們嘗試使所有滿足給定級別順序遍歷的二叉樹都成為天真的方法。 然後檢查樹是否代表二進制搜索樹。 但是此操作將非常昂貴。 首先,我們將建造許多樹木。 然後,該算法需要檢查所形成的樹是否為BST。 因此,我們需要做一些不需要構造樹的事情。

高效方法

一種有效的方法將存儲在級別順序遍歷中出現的每個元素的邊界。 這些邊界表示其子樹元素可以位於的邊界。 如果我們談論一個節點,它將有一個最小值和最大值。 左子樹可以包含從最小綁定到當前節點value-1的元素。 而右側子樹中的元素的範圍可以從當前節點值+1到最大界限。

因此,我們將使用一個隊列,在該隊列中,如果我們能夠遍歷所有節點,則將繼續插入具有這些邊界的元素。 我們說給定的級別順序遍歷可以表示BST,否則不能表示BST。 該算法與檢查二叉樹是否為BST的算法非常相似?

推薦碼

用於檢查給定數組是否可以表示二進制搜索樹的級別順序遍歷的C ++代碼

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    int mn;
    int mx;
};

node create(int data, int mn, int mx){
    node tmp;
    tmp.data = data;
    tmp.mn = mn;
    tmp.mx = mx;
    return tmp;
}

bool checkLevelOrderTraversalRepresentBinarySearchTree(vector<int> traversal){
    queue<node> q;
    int i = 0, n = traversal.size();
    q.push(create(traversal[i++], INT_MIN, INT_MAX));

    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
            q.push(create(traversal[i++], now.mn, now.data));
        if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
            q.push(create(traversal[i++], now.data, now.mx));
    }
    return (i == n);
}

int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> traversal(n);
        for(int i=0;i<n;i++)
            cin>>traversal[i];
        cout<<(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no")<<endl;
    }
}
1
6
5 2 7 1 6 9
true

用於檢查給定數組是否可以表示二進制搜索樹的級別順序遍歷的Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int mn;
  int mx;
}

class Main{
  
  static node create(int data, int mn, int mx){
      node tmp = new node();
      tmp.data = data;
      tmp.mn = mn;
      tmp.mx = mx;
      return tmp;
  }
  
  static boolean checkLevelOrderTraversalRepresentBinarySearchTree(int traversal[]){
      Queue<node> q = new LinkedList<node>();
      int i = 0; int n = traversal.length;
      q.add(create(traversal[i++], Integer.MIN_VALUE, Integer.MAX_VALUE));
  
      while(q.size() > 0){
          node now = q.peek();
          q.remove();
          if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
              q.add(create(traversal[i++], now.mn, now.data));
          if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
              q.add(create(traversal[i++], now.data, now.mx));
      }
      return (i == n);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-- > 0){
          int n = sc.nextInt();
          int[] traversal = new int[n];
          for(int i=0;i<n;i++)
              traversal[i] = sc.nextInt();
          System.out.println(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no");
      }
  }
}
1
6
5 2 7 1 6 9
true

複雜度分析

時間複雜度

正如我們簡單地遍曆元素一樣。 在最壞的情況下,我們需要遍歷所有元素,該算法具有線性時間複雜度 上)。

空間複雜度

我們使用隊列來存儲元素,這使得算法具有線性空間複雜度 上).