C ++のルート（または共通の祖先）からのパスに共通ノードを出力します

この問題では、二分木が与えられ、二分木の2つのノードが定義されます。また、ノードのすべての共通の祖先、つまりルートからノードへのトラバーサルからのパスで発生する共通のノードを印刷する必要があります。

二分木 は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは2つの子ノードを持っています。

例

祖先ノード ツリー内の下位レベルのノードに接続されているノードです。

共通の祖先ノード 2つのノードのうち、ツリー内の両方のノードの祖先ノードであるノードです。

たとえば −

上記の二分木では、0と6の共通の祖先を見つける必要があります。

出力 − 3、2

それでは、この問題に基づいて、この問題を解決するためのアルゴリズムを作成しましょう。

アルゴリズム

Step 1 : Find the lowest common ancestor of the two nodes of the given tree. And print it.
Step 2 : Traverse upward to the root node and print all the nodes that come in the path.

例

それでは、この問題の解決策を説明するプログラムを作成しましょう。

#include <iostream>
using namespace std;
struct Node {
   struct Node* left, *right;
   int key;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
   if (root == NULL)
      return NULL;
   if (root->key == n1 || root->key == n2)
      return root;
   Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
   Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
   if (left_lca && right_lca)
      return root;
   return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
   if (root == NULL)
      return false;
   if (root->key == target) {
      cout << root->key << "\t";
      return true;
   }
   if (printAncestorNodes(root->left, target) ||
   printAncestorNodes(root->right, target)) {
      cout << root->key << "\t”;
      return true;
   }
   return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
   struct Node* LCA = LowestCommonAncestors(root, first, second);
   if (LCA == NULL)
      return false;
   printAncestorNodes(root, LCA->key);
}
int main(){
   Node* root = insertNode(24);
   root->left = insertNode(8);
   root->right = insertNode(69);
   root->left->left = insertNode(12);
   root->left->right = insertNode(41);
   root->right->left = insertNode(50);
   root->right->right = insertNode(3);
   root->left->left->left = insertNode(22);
   root->right->left->left = insertNode(10);
   root->right->left->right = insertNode(6);
   if (printcommonAncestors(root, 6, 3) == false)
      cout << "No Common nodes";
   return 0;
}

出力

69 24