이진 트리 노드의 K 번째 조상

문제 정책

“이진 트리 노드의 K 번째 조상”문제는 이진 트리 및 노드. 이제이 노드의 k 번째 조상을 찾아야합니다. 모든 노드의 조상은 노드의 루트에서 부모까지의 경로에있는 노드입니다.

예

핀

2nd ancestor of 4 is 7

접근

문제는 주어진 노드의 k 번째 조상을 인쇄하도록 요청합니다. 조상은 루트에서 노드의 경로로 오는 노드에 불과합니다. 노드의 부모는 조상이기도합니다.

간단하고 쉬운 해결책은 BFS. 이 솔루션은 쉽고 효율적이지만 먼저 각 노드의 부모를 트리에 저장해야합니다. 그런 다음 문제는 단순히 트리 k 거리에서 위로 이동하는 것으로 요약됩니다. 따라서 노드의 자식을 푸시하는 대신. 각 노드의 부모 만 푸시합니다.

그러나이 솔루션에서는 위에서 설명한 접근 방식을 사용하는 대신. 우리는 DFS 기반 접근. DFS 기반 접근 방식에서는 역 추적을 활용하고 있습니다. 트리에서 노드를 찾으면 재귀는이 재귀 함수를 호출 한 함수로 계속 이동합니다. 따라서 k 단계 뒤로 이동하면 레벨에서 노드를 인쇄합니다. 그것이 우리의 k 번째 조상이기 때문에 null을 반환합니다.

동일한 접근 방식이 이진 트리의 inorder 후계자.

암호

이진 트리에서 노드의 K 번째 조상을 찾는 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

바이너리 트리에서 노드의 K 번째 조상을 찾는 자바 코드

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

복잡성 분석

시간 복잡성

의 위에), 최악의 경우 필요한 노드를 찾기 전에 모든 노드를 통과해야 할 수 있기 때문입니다.

공간 복잡성

의 위에), 재귀 함수에 사용되는 컴파일러 스택 때문입니다.