数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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
更新于: 2020年1月3日
105 次浏览
广告