C++でリーフノードから距離kにあるすべてのノードを出力します

この問題では、二分木と数Kが与えられます。葉のノードからkの距離にある木のすべてのノードを印刷する必要があります。

二分木 は、各ノードに最大2つのノード（1/2 /なし）がある特別なツリーです。

リーフノード 二分木のは、ツリーの最後にあるノードです。

この問題では、リーフノードからの距離はリーフノードよりも高いレベルのノードです。レベル4のリーフノードから距離2のノードがレベル2になるとします。

問題を理解するために例を見てみましょう

K =2

出力 − 6 9.

この問題を解決するために、ツリーをトラバースします。すべては、リーフノードに到達するレベルごとにすべての親ノードセット（祖先ノードとも呼ばれます）を格納します。ここで、リーフノードからkの距離にある祖先を印刷します。訪問したノードのトラバーサルマーキングは重複を避けるために重要ですが、この目的のためにブール配列を使用します-

コードはツリートラバーサルのみを使用するため、複雑さはnに比例します。時間計算量： O（n）

例

私たちの論理を説明するプログラム-

#include <iostream>
using namespace std;
#define MAX_HEIGHT 10000
struct Node {
   int key;
   Node *left, *right;
};
Node* insertNode(int key){
   Node* node = new Node;
   node->key = key;
   node->left = node->right = NULL;
   return (node);
}
void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k){
   if (node==NULL) return;
   path[pathLen] = node->key;
   visited[pathLen] = false;
   pathLen++;
   if (node->left == NULL && node->right == NULL && pathLen-k-1 >= 0 && visited[pathLen-k-1] == false){
      cout<<path[pathLen-k-1]<<"\t";
      visited[pathLen-k-1] = true;
      return;
   }
   nodesKatDistance(node->left, path, visited, pathLen, k);
   nodesKatDistance(node->right, path, visited, pathLen, k);
}
void printNodes(Node* node, int k){
   int path[MAX_HEIGHT];
   bool visited[MAX_HEIGHT] = {false};
   nodesKatDistance(node, path, visited, 0, k);
}
int main(){
   Node * root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(9);
   root->left->right = insertNode(4);
   root->right->left = insertNode(8);
   root->right->right = insertNode(10);
   root->right->left->left = insertNode(5);
   root->right->left->right = insertNode(1);
   int k = 2 cout<<"All nodes at distance "<<k<<" from leaf node are:\n";
   printNodes(root, k);
   return 0;
}

出力

リーフノードから距離2にあるすべてのノードは-

6 9