已知在以二叉链表存储的二叉树BT中,p和q指向二叉树中两个不同的结点,试编写一算法,求包含p和q所指结点的最小子树
时间: 2024-03-21 10:40:37 浏览: 217
编写算法交换二叉树中所有结点的左右子树.doc
5星 · 资源好评率100%
可以使用递归的方法来解决该问题:
1. 如果p或q为NULL,则返回NULL。
2. 如果当前结点root等于p或q,那么最小子树就是root本身,返回root。
3. 分别递归左右子树,得到left和right。
4. 如果left和right都不为NULL,说明p和q分别在root的左右子树中,那么root就是最小子树,返回root。
5. 如果left为NULL,那么最小子树在右子树中,返回right。
6. 如果right为NULL,那么最小子树在左子树中,返回left。
下面是算法的代码实现:
```
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (root == NULL || p == NULL || q == NULL) {
return NULL;
}
if (root == p || root == q) {
return root;
}
struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) {
return root;
} else if (left == NULL) {
return right;
} else {
return left;
}
}
```
阅读全文