Kth прародител на възел в двоично дърво  


Ниво на трудност Трудно
Често задавани в Амазонка Google
Двоично дърво Дърво Обръщане на дърво

Декларация за проблема  

Проблемът „Kth предшественик на възел в двоично дърво“ гласи, че сте получили двоично дърво и възел. Сега трябва да намерим k-тия предшественик на този възел. Предшественик на всеки възел са възлите, които се намират по пътя от корена до родителя на възела.

Пример  

Kth прародител на възел в двоично дървощифт  

2nd ancestor of 4 is 7

Подход  

Проблемът иска да отпечата k-тия предшественик на даден възел. Предшественикът не е нищо друго освен възлите, които идват по пътя на възела от корена. Родителят на възел също е негов предшественик.

Лесно и лесно решение е да се използва BFS. Това решение е лесно и ефективно, но изисква първо да съхраняваме родителя на всеки възел в дървото. Тогава проблемът просто се свежда до придвижване нагоре на дървото k разстояние. Така че вместо да изтласквате децата на възлите. Ще избутаме само родителя на всеки възел.

Но в това решение, вместо да се придържаме към подхода, обсъден по-горе. ще използваме a DFS базиран подход. В подхода, базиран на DFS, ние се възползваме от обратното проследяване. След като намерим възела в дървото, рекурсията продължава да се връща към функцията, която е нарекла тази рекурсивна функция. Така че, когато преместваме k стъпки назад, отпечатваме възела на нивото. Защото това е нашият kth предшественик и връщане null.

Вижте също
Намерете максимална сума на ниво в двоично дърво

Същият подход се използва в inorder наследник на двоичното дърво.

код  

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

Анализ на сложността  

Сложност във времето

НА), тъй като в най-лошия случай може да се наложи да прекоси всички възли, преди които да намерим необходимия възел.

Вижте също
Максимално появяващ се знак

Сложност на пространството

НА), поради стека на компилатора, който се използва за рекурсивните функции.