二分木のノードのK番目の祖先


難易度 ハード
よく聞かれる Amazon (アマゾン) Google
二分木 ツリートラバーサル

問題文

「二分木のノードのK番目の祖先」という問題は、 二分木 およびノー​​ド。 次に、このノードのk番目の祖先を見つける必要があります。 任意のノードの祖先は、ノードのルートから親へのパス上にあるノードです。

二分木のノードのK番目の祖先

2nd ancestor of 4 is 7

アプローチ

この問題は、特定のノードのk番目の祖先を出力するように要求します。 祖先は、ルートからノードのパスに入るノードに他なりません。 ノードの親はその祖先でもあります。

シンプルで簡単な解決策は使用することです BFS。 このソリューションも簡単で効率的ですが、最初に各ノードの親をツリーに格納する必要があります。 次に、問題は単純に、ツリーkの距離を上に移動することになります。 したがって、ノードの子をプッシュする代わりに。 各ノードの親のみをプッシュします。

しかし、このソリューションでは、上記のアプローチを採用する代わりに。 を使用します DFS ベースのアプローチ。 DFSベースのアプローチでは、バックトラックを利用しています。 ツリーでノードが見つかると、再帰はこの再帰関数を呼び出した関数に戻り続けます。 したがって、kステップ戻ると、そのレベルでノードが出力されます。 それが私たちのk番目の祖先であり、nullを返すためです。

同じアプローチがで使用されます 二分木の順序付けられた後継者.

コード

二分木でノードの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番目の祖先を見つけるJavaコード

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

複雑さの分析

時間の複雑さ

オン)、最悪の場合、必要なノードを見つける前にすべてのノードをトラバースする必要がある可能性があるためです。

スペースの複雑さ

オン)、再帰関数に使用されているコンパイラスタックのため。