Kth บรรพบุรุษของโหนดในไบนารีทรี  


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน Google
ต้นไม้ไบนารี ต้นไม้ ทรีทราเวอร์ซัล

คำชี้แจงปัญหา  

ปัญหา“ บรรพบุรุษ K ของโหนดในไบนารีทรี” ระบุว่าคุณได้รับไฟล์ ต้นไม้ไบนารี และโหนด ตอนนี้เราต้องหาบรรพบุรุษ kth ของโหนดนี้ บรรพบุรุษของโหนดใด ๆ คือโหนดที่อยู่บนเส้นทางจากรูทไปยังพาเรนต์ของโหนด

ตัวอย่าง  

Kth บรรพบุรุษของโหนดในไบนารีทรีหมุด  

2nd ancestor of 4 is 7

เข้าใกล้  

ปัญหาขอให้พิมพ์บรรพบุรุษ kth ของโหนดที่กำหนด บรรพบุรุษไม่ใช่อะไรนอกจากโหนดที่เข้ามาในเส้นทางของโหนดจากราก พาเรนต์ของโหนดยังเป็นบรรพบุรุษของโหนด

วิธีแก้ปัญหาที่ง่ายและสะดวกคือการใช้ BFS. โซลูชันนี้ง่ายและมีประสิทธิภาพ แต่เราต้องจัดเก็บพาเรนต์ของแต่ละโหนดไว้ในทรีก่อน จากนั้นปัญหาก็จะเดือดจนขยับขึ้นในระยะต้นไม้ k ดังนั้นแทนที่จะผลักลูกของโหนด เราจะดันพาเรนต์ของแต่ละโหนดเท่านั้น

แต่ในการแก้ปัญหานี้แทนที่จะเป็นไปตามแนวทางที่กล่าวไว้ข้างต้น เราจะใช้ไฟล์ DFS ตามแนวทาง ในแนวทางที่ใช้ DFS เรากำลังใช้ประโยชน์จากการย้อนรอย เมื่อเราพบโหนดในทรีการเรียกซ้ำจะย้ายกลับไปที่ฟังก์ชันซึ่งเรียกว่าฟังก์ชันการเรียกซ้ำ ดังนั้นเมื่อเราเลื่อน k ไปข้างหลังเราจึงพิมพ์โหนดที่ระดับ เพราะนั่นคือบรรพบุรุษ kth ของเราและคืนค่าว่าง

ดูสิ่งนี้ด้วย
ค้นหาผลรวมระดับสูงสุดใน Binary Tree

วิธีการเดียวกันนี้ใช้ในไฟล์ ตามลำดับตัวตายตัวแทนของต้นไม้ไบนารี.

รหัส  

รหัส 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

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

บน)เนื่องจากในกรณีที่เลวร้ายที่สุดอาจต้องสำรวจโหนดทั้งหมดก่อนที่เราจะพบโหนดที่ต้องการ

ดูสิ่งนี้ด้วย
อักขระที่เกิดขึ้นสูงสุด

ความซับซ้อนของอวกาศ

บน)เนื่องจากคอมไพเลอร์สแต็กซึ่งถูกใช้สำหรับฟังก์ชันเรียกซ้ำ