ਬਾਈਨਰੀ ਟਰੀ ਵਿਚ ਇਕ ਨੋਡ ਦਾ Kth ਪੂਰਵਜ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਗੂਗਲ
ਬਾਈਨਰੀ ਟਰੀ ਟ੍ਰੀ ਟ੍ਰੀ ਟ੍ਰੈਵਲ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਬਾਈਨਰੀ ਟ੍ਰੀ ਦੇ ਨੋਡ ਦੇ Kth ਪੂਰਵਜ" ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਏ ਬਾਈਨਰੀ ਟਰੀ ਅਤੇ ਇਕ ਨੋਡ ਹੁਣ ਸਾਨੂੰ ਇਸ ਨੋਡ ਦੇ kth ਪੂਰਵਜ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਕਿਸੇ ਵੀ ਨੋਡ ਦਾ ਪੂਰਵਜ ਨੋਡ ਹੁੰਦੇ ਹਨ ਜੋ ਜੜ੍ਹ ਤੋਂ ਨੋਡ ਦੇ ਮਾਪਿਆਂ ਦੇ ਰਸਤੇ ਤੇ ਹੁੰਦੇ ਹਨ.

ਉਦਾਹਰਨ

ਬਾਈਨਰੀ ਟਰੀ ਵਿਚ ਇਕ ਨੋਡ ਦਾ Kth ਪੂਰਵਜ

2nd ancestor of 4 is 7

ਪਹੁੰਚ

ਸਮੱਸਿਆ ਇੱਕ ਦਿੱਤੇ ਨੋਡ ਦੇ kth ਪੂਰਵਜ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਨ ਲਈ ਕਹਿੰਦੀ ਹੈ. ਇੱਕ ਪੂਰਵਜ ਨੋਡਾਂ ਤੋਂ ਇਲਾਵਾ ਕੁਝ ਵੀ ਨਹੀਂ ਹੁੰਦਾ ਜੋ ਜੜ੍ਹਾਂ ਤੋਂ ਨੋਡ ਦੇ ਰਸਤੇ ਆਉਂਦੇ ਹਨ. ਨੋਡ ਦਾ ਮਾਪਾ ਵੀ ਇਸਦਾ ਪੂਰਵਜ ਹੁੰਦਾ ਹੈ.

ਇੱਕ ਸਧਾਰਣ ਅਤੇ ਸੌਖਾ ਹੱਲ ਹੈ ਵਰਤੋਂ BFS. ਇਹ ਹੱਲ ਅਸਾਨ ਅਤੇ ਕੁਸ਼ਲ ਵੀ ਹੈ ਪਰ ਸਾਨੂੰ ਹਰ ਨੋਡ ਦੇ ਮਾਪਿਆਂ ਨੂੰ ਪਹਿਲਾਂ ਦਰੱਖਤ ਵਿਚ ਸਟੋਰ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਫਿਰ ਸਮੱਸਿਆ ਦਰੱਖਤ ਦੀ ਦੂਰੀ 'ਤੇ ਵੱਧਣ ਲਈ ਸਿਰਫ ਹੇਠਾਂ ਉਬਲਦੀ ਹੈ. ਇਸ ਲਈ ਬੱਚਿਆਂ ਨੂੰ ਧੱਕਾ ਕਰਨ ਦੀ ਬਜਾਏ. ਅਸੀਂ ਸਿਰਫ ਹਰੇਕ ਨੋਡ ਦੇ ਮਾਪਿਆਂ ਨੂੰ ਧੱਕਾ ਦੇਵਾਂਗੇ.

ਪਰ ਇਸ ਹੱਲ ਵਿੱਚ, ਉਪਰੋਕਤ ਵਿਚਾਰ ਕੀਤੀ ਪਹੁੰਚ ਨਾਲ ਜਾਣ ਦੀ ਬਜਾਏ. ਅਸੀਂ ਇੱਕ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ ਡੀਐਫਐਸ ਅਧਾਰਤ ਪਹੁੰਚ ਡੀਐਫਐਸ ਅਧਾਰਤ ਪਹੁੰਚ ਵਿਚ, ਅਸੀਂ ਬੈਕਟ੍ਰੈਕਿੰਗ ਦਾ ਲਾਭ ਲੈ ਰਹੇ ਹਾਂ. ਇੱਕ ਵਾਰ ਜਦੋਂ ਸਾਨੂੰ ਰੁੱਖ ਵਿੱਚ ਨੋਡ ਮਿਲ ਜਾਂਦਾ ਹੈ, ਦੁਬਾਰਾ ਵਾਪਸੀ ਫੰਕਸ਼ਨ ਵਿੱਚ ਵਾਪਸ ਚਲਦੀ ਰਹਿੰਦੀ ਹੈ ਜਿਸ ਨੂੰ ਇਸ ਰਿਕਰਸਿਵ ਫੰਕਸ਼ਨ ਕਹਿੰਦੇ ਹਨ. ਇਸ ਲਈ ਜਦੋਂ ਅਸੀਂ k ਕਦਮ ਪਿੱਛੇ ਹਟਦੇ ਹਾਂ, ਅਸੀਂ ਪੱਧਰ 'ਤੇ ਨੋਡ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਦੇ ਹਾਂ. ਕਿਉਂਕਿ ਇਹ ਸਾਡੇ kth ਪੂਰਵਜ ਹੈ ਅਤੇ ਵਾਪਸੀ ਨਲ.

ਵਿੱਚ ਉਹੀ ਪਹੁੰਚ ਵਰਤੀ ਜਾਂਦੀ ਹੈ ਬਾਈਨਰੀ ਟਰੀ ਦੇ ਅੰਦਰੂਨੀ ਉਤਰਾਧਿਕਾਰੀ.

ਕੋਡ

ਬਾਈ + ਟਰੀ ਵਿਚ ਕਿਸੇ ਨੋਡ ਦੇ Kth ਪੂਰਵਜ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ C ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਸਭ ਤੋਂ ਮਾੜੇ ਹਾਲਾਤ ਵਿੱਚ ਉਨ੍ਹਾਂ ਸਾਰੇ ਨੋਡਾਂ ਨੂੰ ਪਾਰ ਕਰਨਾ ਪੈ ਸਕਦਾ ਹੈ ਜਿਸ ਤੋਂ ਪਹਿਲਾਂ ਸਾਨੂੰ ਲੋੜੀਂਦਾ ਨੋਡ ਲੱਭਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕੰਪਾਈਲਰ ਸਟੈਕ ਦੇ ਕਾਰਨ ਜੋ ਰਿਕਰਸਿਵ ਫੰਕਸ਼ਨਾਂ ਲਈ ਵਰਤੀ ਜਾ ਰਹੀ ਹੈ.