使用c++ 设计一个算法,在给定的整数二叉排序树上找出任意两个不同结点x和y的最近公共祖先(LCA)。其中结点x是指关键字为x的结点(假设x和y结点均在二叉排序树中)。
时间: 2024-12-24 11:38:08 浏览: 4
要在C++中设计一个算法找到整数二叉排序树(BST)中两个不同节点X和Y的最近公共祖先(LCA),可以采用自底向上、分治的思想,利用二叉搜索树的性质简化查找过程。首先从根节点开始,对比目标节点X和Y的值,如果它们都在左子树或右子树中,那么LCA也在相同的子树中;如果一个在左子树,另一个在右子树,说明根节点就是LCA。这个过程递归地应用到X和Y所在的子树直到找到它们的LCA。
以下是一个简单的C++实现:
```cpp
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) {
return root;
}
int valP = p->val, valQ = q->val;
if (valP < root->val && valQ < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (valP > root->val && valQ > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else {
return root;
}
}
};
```
在这个解决方案中,`lowestCommonAncestor` 函数接收一个当前节点、目标节点X和Y。如果当前节点为空或者正是目标节点之一,就返回当前节点;否则,根据X和Y的值与当前节点值的关系,确定是在左子树还是右子树中寻找LCA。
阅读全文