Kth аҷдоди гиреҳ дар дарахти дуӣ


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Google
Дарахти дуӣ Дарахт Траверсал дарахт

Изҳороти мушкилот

Масъалаи "Аҷдодони Kth гиреҳ дар дарахти дуӣ" мегӯяд, ки ба шумо a дарахти дуӣ ва гиреҳ. Ҳоло мо бояд аҷдоди kth-и ин гиреҳро пайдо кунем. Аҷдоди ягон гиреҳ гиреҳҳоест, ки дар роҳ аз реша то волидайни гиреҳ ҷойгиранд.

мисол

Kth аҷдоди гиреҳ дар дарахти дуӣ

2nd ancestor of 4 is 7

усул

Масъала дархост мекунад, ки гузаштаи kth гиреҳи додашуда чоп карда шавад. Аҷдод чизе нест, ҷуз гиреҳҳо, ки дар роҳи гиреҳ аз реша меоянд. Волидайни гиреҳ низ гузаштаи он аст.

Як ҳалли оддӣ ва осон истифода аст BFS. Ин ҳалли осон ва муассир аст, аммо аз мо талаб мекунад, ки аввал волидайни ҳар як гиреҳро дар дарахт нигоҳ дорем. Он гоҳ, ки мушкилот танҳо ба боло рафтан дар масофаи k меафтад. Пас ба ҷои тела додани фарзандони гиреҳҳо. Мо танҳо волидайни ҳар як гиреҳро тела медиҳем.

Аммо дар ин ҳалли масъала, ба ҷои рафтан бо усули дар боло баррасишуда. мо истифода мебарем DFS равиши асоснок. Дар равиши ба DFS асосёфта, мо аз бозгашт истифода мебарем. Пас аз пайдо кардани гиреҳи дарахт, рекурсия ба функсияе, ки ин функсияи рекурсивӣ меномид, ҳаракат мекунад. Пас, вақте ки мо k қадамро ба қафо мекашем, гиреҳро дар сатҳи чоп мекунем. Азбаски ин аҷдоди kth-и мост ва бозгашт ба сифр.

Худи ҳамин равиш дар дар вориси дарахти дуӣ.

рамз

Коди 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

Рамзи Java барои ёфтани 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

Таҳлили мураккабӣ

Мураккабии вақт

О (Н), зеро дар ҳолати бадтарин метавонад ҳамаи гиреҳҳоро убур кунад, ки пеш аз он мо гиреҳи лозимиро пайдо кунем.

Мураккабии фазо

О (Н), аз сабаби стеки компилятор, ки барои функсияҳои рекурсивӣ истифода мешавад.