不允許修改BST時BST中的第K個最大元素


難度級別
經常問 亞馬遜 思科 谷歌 UHG Optum
二進制搜索樹 二叉樹

問題陳述

“不允許對BST進行修改時,BST中的第K個最大元素”指出已為您提供了一個二進制搜索樹,您需要找到第k個最大元素。 這意味著當二分搜索樹的所有元素都按降序排列時。 然後,我們需要從序列中返回第k個元素。

輸入

不允許修改BST時BST中的第K個最大元素

k = 4

3

說明:上面顯示了樹的圖像。 我們需要找到第4大元素。 因此,如果我們按升序排列它們,則它們是{1、2、3、4、5、6}。 因此,第4大元素是第3小元素。 因此,我們返回3作為輸出。

不允許修改BST時在BST中找到第K個最大元素的方法

我們已經做了一個類似的問題,在哪裡找到了 第k個最小元素 在BST中。 問題只是對它的修改。 在上一篇文章中,我們討論了該問題的解決方案。 第一種方法是修改樹數據結構。 另一個是對二進制搜索樹進行有序遍歷,並繼續計算節點數。 由於上一個問題是返回第k個最小值。 我們只計算節點數,一旦計數等於k,就返回該節點上的值。

天真的方法

這裡的情況有些不同。 我們需要找到第k個最大元素,我們首先可以找到樹中節點的總數,然後從節點總數中減去k-1。 現在我們找到n-k + 1個最小的節點,其中n是二叉搜索樹中的節點總數。 但是這種方法需要兩次或兩次 遍歷 在樹上。

高效方法

如果我們可以按降序找到節點,則可以有效地解決該問題。 這樣,我們將無需查找樹中的節點總數。 一種有效的方法是對樹進行逆序遍歷。 二叉搜索樹的逆序遍歷以降序遍歷樹。 因此,在按順序進行反向操作時,我們將繼續對節點進行計數。 當計數等於k時,我們返回該節點上的值。

推薦碼

不允許修改BST時使用C ++代碼在BST中查找第K個最大元素

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node *left;
    node *right;
} ;
node* create(int data){
    node * tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}
// normally insert the node in BST
node* insert(node* root, int x)
{
    if (root == NULL)
        return create(x);
    if(x<root->data)
        root->left = insert(root->left, x);
    else if(x>root->data)
        root->right = insert(root->right, x);
    return root;
}
node* findKthLargest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *right = findKthLargest(root->right, k);
    if(right)
        return right;
    // if current element is kth largest
    if(k==1)
        return root;
    // if the kth largest is not found in the left subtree
    // search in left subtree
    k--;
    return findKthLargest(root->left, k);
}
int main()
{
    node *root = NULL;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int element;cin>>element;
        root = insert(root, element);
    }
    int k;cin>>k;
    node* res = findKthLargest(root, k);
    if(res == NULL)
        cout<<"No kth largest found";
    else
        cout<<"Kth largest element is "<<res->data;
}
6
3 2 1 5 4 6
4
Kth largest element is 3

不允許修改BST時在BST中找到第K個最大元素的Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static int count;
  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = null;
      tmp.right = null;
      return tmp;
  }
 
  static node insert(node root, int x)
  {
      if (root == null)
          return create(x);
      if(x<root.data)
          root.left = insert(root.left, x);
      else if(x>root.data)
          root.right = insert(root.right, x);
      return root;
  }
 
  static node findKthLargest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node right = findKthLargest(root.right, k);
      if(right != null)
          return right;
      count++;
      // if current element is kth largest
      if(k==count)
          return root;
      // if the kth largest is not found in the left subtree
      // search in left subtree
      return findKthLargest(root.left, k);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      for(int i=0;i<n;i++){
          int element = sc.nextInt();
          root = insert(root, element);
      }
      int k = sc.nextInt();
      count = 0;
      node res = findKthLargest(root, k);
      if(res == null)
          System.out.println("No kth largest found");
      else
          System.out.println("Kth largest element is "+res.data);
  }
}
6
3 2 1 5 4 6
4
Kth largest element is 3

複雜度分析

時間複雜度

上), 因為我們只是遍歷了 BST,並且由於BST只有N個節點。 我們已經實現了O(N)的線性時間複雜度。

空間複雜度

O(1), 我們僅使用了恆定的額外空間。 因此,只有該算法具有恆定的空間複雜度,而整個程序卻具有線性的空間複雜度。 因為我們正在存儲N個二叉樹節點。