使用 C++ 打印从根节点到指定节点路径上的公共节点

在这个问题中，我们给定一棵二叉树，并定义了二叉树中的两个节点。我们需要打印这两个节点的公共祖先，即从根节点到这两个节点的遍历路径中出现的公共节点。

二叉树是一种特殊的树，其每个节点最多有两个子节点。因此，每个节点要么是叶子节点，要么有一个或两个子节点。

例如，

祖先节点是指在树中连接到较低级别节点的节点。

两个节点的公共祖先节点是指在树中是这两个节点的祖先节点的节点。

例如 -

在上面的二叉树中，我们需要找到节点 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

sudhir sharma

更新于: 2020年1月3日

105 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习