İkili ağacdakı bir düyünün atası

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon google
İkili ağac Ağac Ağacın keçidiBaxılıb 30

Problem bəyanat

Problem "İkili ağacdakı bir düyünün atası K" sizə a ikili ağac və bir qovşaq. İndi bu düyünün kth əcdadını tapmaq lazımdır. Hər hansı bir düyünün əcdadı kökdən düyünün ana tərəfinə gedən yolda yerləşən qovşaqlardır.

misal

İkili ağacdakı bir düyünün atasıPin

2nd ancestor of 4 is 7

Yanaşma

Problem, verilən bir düyünün kth əcdadını çap etməyi xahiş edir. Bir əcdad, kökündən düyünün yoluna gələn qovşaqlardan başqa bir şey deyildir. Bir düyünün valideyn də atasıdır.

Sadə və asan bir həll istifadə etməkdir BFS. Bu həll asan və səmərəlidir, lakin əvvəlcə hər bir düyünün ana hissəsini ağacda saxlamağımızı tələb edir. Sonra problem sadəcə k məsafəsində ağacdan yuxarıya doğru irəliləyir. Beləliklə, qovşaqların uşaqlarını itələmək əvəzinə. Yalnız hər bir düyünün valideynini itələyəcəyik.

Ancaq bu həll yolunda, yuxarıda müzakirə edilən yanaşma ilə getmək yerinə. istifadə edəcəyik DFS əsaslı yanaşma. DFS əsaslı yanaşmada geri çəkilmədən faydalanırıq. Ağacdakı düyünü tapdıqdan sonra rekursiya bu rekursiv funksiya adlanan funksiyaya qayıdır. Beləliklə, k addım geri çəkildikdə, qovşaq səviyyəsində çap edirik. Çünki bu bizim kth əcdadımızdır və geri dönər.

Eyni yanaşma ikili ağacın varisi.

Kodu

İkili ağacdakı bir düyünün Kth əcdadını tapmaq üçün C ++ kodu

#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

İkili ağacdakı bir düyünün Kth əcdadını tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ən pis halda lazımi nodu tapdığımız bütün qovşaqları keçməli ola bilərik.

Kosmik Mürəkkəblik

O (N), rekursiv funksiyalar üçün istifadə olunan kompilyator yığını səbəbindən.

Translate »