Ստուգեք, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Accenture Amazon Մոնոտիպ լուծումներ PayPal Սինոփսիս
Երկուական որոնման ծառ Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«Ստուգեք, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա» խնդիրը նշում է, որ ձեզ տրված է երկուական որոնման ծառի նախնական պատվեր: Եվ դուք պետք է պարզեք, արդյոք բոլոր ոչ տերլազարդ հանգույցները պարունակում են միայն մեկ երեխա: Այստեղ մենք նաև համարում ենք, որ տրված մուտքի բոլոր հանգույցներն ունեն հստակ մեծություններ:

Օրինակ

Ստուգեք, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա

 

Preorder Traversal: 6 15 7 9 11
Yes

Բացատրությունը. Ինչպես տեսնում ենք վերևում նկարում, տրված նախնական պատվերի անցումով ծառը յուրաքանչյուր ներքին հանգույցի համար ունի մեկ երեխա: Այսպիսով արդյունքը այո է:

Մոտեցում ՝ ստուգելու, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա

Նախնական պատվերի անցում նշանակում է, որ արմատը նախապատվությունը տրվում է և տպվում է նրա ձախ և աջ ենթատեսակներից առաջ: Այսպիսով, արմատից հետո տարրերը կամ ավելի փոքր են կամ ավելի մեծ, քան արմատը: Այսպիսով, եթե մենք պետք է ստուգենք, արդյոք տրված հաջորդականությունը նախադրյալն է a- ի Երկուական որոնման ծառ, Մենք կարող ենք օգտագործել երկու տեղադրված օղակ ՝ ստուգելու համար, թե արդյոք կարող ենք ստեղծել տրված հաջորդականությամբ երկուական որոնման ծառ:

Միամիտ մոտեցում

Ինչպես արդեն քննարկեցինք, այդ նախնական պատվերի անցումը պարունակում է վերևում գտնվող արմատը և ձախ և աջ ենթատեսակի տպագրությունից հետո: Այժմ այս գործողությունն ավարտված է հետադարձաբար մինչեւ ծառի բոլոր հանգույցները ծածկվեն: Այսպիսով, մենք կարող ենք ստուգել, ​​արդյոք տվյալ հաջորդականությունը ներկայացնում է BST, մենք գործարկում ենք երկու ներդիր օղակ, որտեղ արտաքին օղակն օգտագործվում է արմատ ընտրելու համար: Եվ տեղադրված օղակը ստուգում է, թե արդյոք դրանից հետո տարրերը կարող են ներկայացնել նրա ձախ և աջ ենթատեսակները: Դրա համար մենք ստուգում ենք, եթե մինչև որոշակի ցուցանիշ բոլոր տարրերն ավելի փոքր են, քան ընտրված տարրը: Եվ դրանից հետո տարրերն ավելի մեծ են, քան ընտրված տարրը: Այժմ, մենք կարող ենք փոփոխել այս մոտեցումը `ըստ մեր օգտագործման դեպքի:

Տեսնենք, թե ինչպես կարող ենք փոփոխել ալգորիթմը ՝ ստուգելու համար, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա: Եթե ​​BST- ի ներքին երեխան ունի մեկ երեխա: Սա նշանակում է, որ յուրաքանչյուր ներքին հանգույց կարող է ունենալ ինչպես ձախ, այնպես էլ աջ ենթա-ծառ: Այն միաժամանակ չի պարունակի երկու ենթաթևերը: Այսպիսով, ամփոփելու համար մեր ալգորիթմը: Մենք օգտագործում ենք երկու տեղադրված օղակ, որտեղ արտաքին օղակը տարր է ընտրում: Այնուհետև տեղադրված օղակն օգտագործվում է ստուգելու համար, թե արդյոք դրանից հետո եկող տարրերը պատկանում են ենթա ծառերից որևէ մեկին: Նախկինում մենք ունեինք որոշակի ցուցանիշ, մինչ այդ տարրերը արմատից փոքր էին, որից հետո տարրերը դրանից մեծ էին: Հիմա մենք ոչ մի նման ցուցանիշ չենք գտնի: Բայց այս մեթոդը բավականաչափ արդյունավետ չէ, քանի որ այն ունի O (N ^ 2) բազմանդամ-ժամանակի բարդություն:

Արդյունավետ մոտեցում

Մինչ այժմ մենք հստակ նշել ենք մեկ կետ, որ ցանկացած հանգույցի բոլոր երեխաները, այս խնդրի համաձայն, կլինեն կամ ավելի փոքր կամ ավելի մեծ, քան ընթացիկ հանգույցը: Այսպիսով, որպեսզի ստուգվի, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա, մենք գտնում ենք ընթացիկ հանգույցի հաջորդ նախնական պատվերը: Դրանից հետո մենք գտնում ենք ընթացիկ հանգույցի վերջին նախնական պատվերի իրավահաջորդը: Եթե ​​երկու ժառանգներն էլ ավելի փոքր են, քան ընթացիկ հանգույցը կամ ավելի մեծ են, քան ընթացիկ հանգույցը: Հետո մենք այլ կերպ ենք գործում, մենք գիտենք, որ ընթացիկ հանգույցն ունի և՛ ձախ, և՛ աջ ենթատեսակ, քանի որ տարրերից մեկն ավելի փոքր է, քան ընթացիկ հանգույցը: Եվ մեկ այլ հանգույց ավելի մեծ է, քան ընթացիկ հանգույցը: Այսպիսով, մենք վերադարձնում ենք կեղծ կամ -1 ըստ մեր պահանջի:

Կոդ

C ++ ծածկագիր `ստուգելու համար, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա

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

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

Java կոդ ՝ ստուգելու համար, արդյոք BST- ի յուրաքանչյուր ներքին հանգույց ունի հենց մեկ երեխա

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N), քանի որ մենք պարզապես անցել ենք նախնական պատվերի զանգվածով: Իսկ նախնական պատվերի զանգվածն ունի N տարրեր, ուստի գծային ժամանակի բարդություն:

Տիեզերական բարդություն

O (N), ռեկուրսիվ բուրգի համար պահանջվող տարածություն, և մենք նաև օգտագործեցինք N չափի մուտքային զանգված ՝ նախնական պատվերի հաջորդականությունը պահելու համար: