ორობითი ხის კვანძის Kth


Რთული ტური Hard
ხშირად ეკითხებიან Amazon Google
ორობითი ხე ხე ხის გადაკვეთა

პრობლემის განცხადება

პრობლემა "ორობითი ხის კვანძის Kth" აცხადებს, რომ თქვენ გეძლევათ ა ორობითი ხე და კვანძი. ახლა ჩვენ უნდა ვიპოვოთ ამ კვანძის kth წინაპარი. ნებისმიერი კვანძის წინაპარი არის კვანძები, რომლებიც დევს ფესვიდან კვანძის მშობლისკენ მიმავალ გზაზე.

მაგალითი

ორობითი ხის კვანძის Kth

2nd ancestor of 4 is 7

მიდგომა

პრობლემა ითხოვს მოცემული კვანძის kth წინაპრის დაბეჭდვას. წინაპარი სხვა არაფერია, თუ არა კვანძები, რომლებიც ფესვიდან მოდის კვანძის გზაზე. კვანძის მშობელი ასევე მისი წინაპარია.

მარტივი და მარტივი გამოსავალია გამოყენება Bfs. ეს გამოსავალი არის მარტივი და ეფექტური, მაგრამ ჩვენგან ჯერ უნდა დავიჭიროთ თითოეული კვანძის მშობელი. შემდეგ პრობლემა უბრალოდ იშლება ხის კ მანძილზე გადაადგილებით. ასე რომ, კვანძების შვილების ბიძგის ნაცვლად. ჩვენ მხოლოდ თითოეული კვანძის მშობელს დავაყენებთ.

ამ გადაწყვეტილების ნაცვლად, ზემოთ განხილული მიდგომის ნაცვლად. ჩვენ გამოვიყენებთ ა DFS დაფუძნებული მიდგომა. DFS– ზე დაფუძნებული მიდგომისას, ჩვენ უპირატესობას ვიღებთ უკან დახევაზე. მას შემდეგ, რაც ხეში კვანძს ვიპოვით, რეკურსია ისევ ბრუნდება იმ ფუნქციაზე, რომელსაც ამ რეკურსიულ ფუნქციას უწოდებენ. როდესაც k ნაბიჯებით უკან მივდივართ, კვანძს ვბეჭდავთ დონეზე. იმიტომ, რომ ეს არის ჩვენი წინაპარი და ნულოვანია.

იგივე მიდგომა გამოიყენება ორობითი ხის მემკვიდრე.

კოდი

C ++ კოდი ორობითი ხის კვანძის Kth წინაპრის მოსაძებნად

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

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* tmp = NULL;

node* kthAncestor(node *root, int cur, int &k)
{
  if (root == NULL)
    return NULL;
  if (root->data == cur || (tmp = kthAncestor(root->left,cur,k)) || (tmp = kthAncestor(root->right,cur,k))){
    if(k)k--;
    else if (k == 0){
      cout<<"kth ancestor of "<<cur<<" is "<<root->data;
      return NULL;
    }
    return root;
  }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);
  int k = 2;
  kthAncestor(root, 4, k);
}
kth ancestor of 4 is 7

ჯავის კოდი ორობითი ხის კვანძის Kth წინაპრის მოსაძებნად

import java.util.*;
class node{
  int data;
  node left, right;
}
class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  	static int k = 2;
  static node tmp = null;

  static node kthAncestor(node root, int cur)
  {
    if (root == null)
      return null;
    if ((root.data == cur) || ((tmp = kthAncestor(root.left,cur)) != null) || ((tmp = kthAncestor(root.right,cur)) != null)){
      if(k > 0)k--;
      else if (k == 0){
        System.out.print("kth ancestor of "+cur+" is "+root.data);
        return null;
      }
      return root;
    }
    return null;
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);
    k = 2;
    kthAncestor(root, 4);
  }
}
kth ancestor of 4 is 7

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან უარეს შემთხვევაში შეიძლება ყველა კვანძის გადალახვა მოგიწიოთ, რომლის წინაშეც ჩვენ ვიპოვით საჭირო კვანძს.

სივრცის სირთულე

O (N), შემდგენელი სტეკის გამო, რომელიც გამოიყენება რეკურსიული ფუნქციებისათვის.