利用数据结构完成假设二叉树采用二叉链表方式存储,root指向根结点,p所指结点和q所指结点为二叉树中的两个不同结点,且互不成为根到该结点的路径上的点,编程求解距离它们最近的共同祖先。
时间: 2024-05-05 17:19:10 浏览: 10
好的,让我思考一下。我们可以通过遍历二叉树,找到路径上最后一个公共节点,即为最近的共同祖先。具体的实现步骤如下:
1. 从root节点开始遍历二叉树,求出p节点到根节点的路径;
2. 从root节点开始遍历二叉树,求出q节点到根节点的路径;
3. 对比p和q两个路径,找到最后一个公共节点,即为最近的共同祖先。
以下是实现的伪代码:
```
// 定义二叉树的节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 求p节点到根节点的路径
bool findPath(TreeNode* root, TreeNode* p, vector<TreeNode*>& path) {
if (!root) {
return false;
}
path.push_back(root);
if (root == p) {
return true;
}
if (findPath(root->left, p, path) || findPath(root->right, p, path)) {
return true;
}
path.pop_back(); // 回溯
return false;
}
// 求q节点到根节点的路径
bool findPath(TreeNode* root, TreeNode* q, vector<TreeNode*>& path) {
if (!root) {
return false;
}
path.push_back(root);
if (root == q) {
return true;
}
if (findPath(root->left, q, path) || findPath(root->right, q, path)) {
return true;
}
path.pop_back(); // 回溯
return false;
}
// 找到最近的共同祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path1, path2;
findPath(root, p, path1);
findPath(root, q, path2);
int i = 0;
while (i < path1.size() && i < path2.size() && path1[i] == path2[i]) {
i++;
}
return path1[i - 1];
}
```
希望能帮到你,还有其他问题可以继续问我哦!