Kth جد یک گره در درخت باینری


سطح دشواری سخت
اغلب در آمازون گوگل
درخت باینری درخت عبور از درخت

بیان مسأله

مسئله "Kth جد یک گره در درخت باینری" بیان می کند که به شما یک a داده می شود درخت دودویی و یک گره اکنون باید نیافته kth این گره را پیدا کنیم. نیای هر گره گره هایی است که در مسیر ریشه تا والد گره قرار دارند.

مثال

Kth جد یک گره در درخت باینری

2nd ancestor of 4 is 7

روش

این مسئله می خواهد که جد kth یک گره داده شده را چاپ کند. جد چیزی نیست جز گره هایی که از مسیر ریشه در مسیر گره قرار می گیرند. والد گره نیز جد آن است.

یک راه حل ساده و آسان برای استفاده است BFS. این راه حل آسان و کارآمد است اما ما را ملزم می کند که ابتدا والدین هر گره را در درخت ذخیره کنیم. سپس مسئله به سادگی بالا می رود تا در فاصله درخت k به سمت بالا حرکت کنید. بنابراین به جای فشار دادن به کودکان گره ها. ما فقط والدین هر گره را فشار خواهیم داد.

اما در این راه حل ، به جای اینکه با رویکردی که در بالا بحث شد بروید. ما از a استفاده خواهیم کرد DFS رویکرد مبتنی بر در روش مبتنی بر DFS ، ما از عقبگرد استفاده می کنیم. هنگامی که گره موجود در درخت را پیدا کردیم ، بازگشت به سمت تابعی که این تابع بازگشتی نامیده می شود ، حرکت می کند. بنابراین وقتی k قدم به عقب حرکت می کنیم ، گره را در سطح چاپ می کنیم. زیرا این جد بازگشت ماست و صفر است.

از همین رویکرد در 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

کد جاوا برای یافتن اجداد 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

تحلیل پیچیدگی

پیچیدگی زمان

بر)، زیرا در بدترین حالت ممکن است مجبور به عبور از همه گره هایی باشیم که قبل از آن گره مورد نیاز را پیدا می کنیم.

پیچیدگی فضا

بر)، به دلیل پشته کامپایلر که برای توابع بازگشتی استفاده می شود.