假设二叉树采用二叉链表方式存储,root指向根结点,p所指结点和q所指结点为二叉树中的两个不同结点,且互不成为根到该结点的路径上的点,编程求解距离它们最近的共同祖先。
时间: 2024-05-14 08:16:41 浏览: 98
寻找二叉树两结点最近的祖先
4星 · 用户满意度95%
你好,感谢您对我的提问。对于您的问题,我可以给出以下C++代码实现:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
```
该函数输入为二叉树的根节点指针root,以及需要查找最近共同祖先的两个节点指针p和q。函数会递归地在左子树和右子树中查找p和q的位置,如果p和q都在左子树或右子树,则递归到左子树或右子树查找。如果p和q分别在左子树和右子树,则返回最近公共祖先。如果当先节点为NULL或为p或为q,则说明已经找到了其中一个节点,返回当前节点。
注意,该二叉树为二叉链表方式存储的二叉树(即每个节点包含左右儿子的指针),而不是数组或其他方式存储的二叉树。
希望能够解决您的问题。
阅读全文