C++에서 루트(또는 공통 조상)의 경로에 공통 노드 인쇄

이 문제에서는 이진 트리가 주어지고 이진 트리의 두 노드가 정의됩니다. 그리고 노드의 모든 공통 조상, 즉 루트에서 노드로의 순회 경로에서 발생하는 공통 노드를 인쇄해야 합니다.

이진 트리 모든 노드에 최대 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