用C++编写算法,在二叉排序树中找出任意两个不同节点的最近公共祖先
时间: 2024-02-28 19:52:04 浏览: 21
以下是用C++编写的算法,它使用了递归的方法,在二叉排序树中找出任意两个不同节点的最近公共祖先:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL; // 如果根节点为空,返回NULL
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q); // 如果根节点大于p和q的值,那么p和q在根节点的左子树中,递归左子树
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q); // 如果根节点小于p和q的值,那么p和q在根节点的右子树中,递归右子树
} else {
return root; // 如果根节点的值介于p和q的值之间,那么根节点就是它们的最近公共祖先
}
}
int main() {
TreeNode* root = new TreeNode{6, NULL, NULL};
root->left = new TreeNode{2, NULL, NULL};
root->right = new TreeNode{8, NULL, NULL};
root->left->left = new TreeNode{0, NULL, NULL};
root->left->right = new TreeNode{4, NULL, NULL};
root->left->right->left = new TreeNode{3, NULL, NULL};
root->left->right->right = new TreeNode{5, NULL, NULL};
root->right->left = new TreeNode{7, NULL, NULL};
root->right->right = new TreeNode{9, NULL, NULL};
TreeNode* p = root->left->right->left;
TreeNode* q = root->left->right->right;
TreeNode* lca = lowestCommonAncestor(root, p, q);
cout << "Lowest Common Ancestor of " << p->val << " and " << q->val << " is " << lca->val << endl;
return 0;
}
```
该程序的输出结果是:
```
Lowest Common Ancestor of 3 and 5 is 4
```
其中,root是二叉排序树的根节点,p和q是任意两个不同的节点,lca是它们的最近公共祖先。