已知在以二叉链表存储的二叉树BT中，p和q指向二叉树中两个不同的结点，试编写一算法，求包含p和q所指结点的最小子树。

可以使用递归的思想来解决该问题。首先，我们需要判断当前节点是否为p或q，如果是，那么当前节点就是包含p和q的最小子树。如果不是，那么我们需要分别递归左右子树，找到包含p和q的最小子树。

具体实现的伪代码如下：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left != nullptr && right != nullptr) {
        return root;
    } else if (left != nullptr) {
        return left;
    } else {
        return right;
    }
}

该算法的时间复杂度为$O(n)$，其中n是二叉树中节点的个数。

相关问题

已知在以二叉链表存储的二叉树BT中，p和q指向二叉树中两个不同的结点，试编写一算法，求包含p和q所指结点的最小子树

可以使用递归的方法来解决该问题：

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;
    }
}

用c语言编写已知二叉树采用二叉链表存储结构，设计一个算法，使二叉树中所有结点的左右子树相互交换

好的，您所提出的问题是：如何用c语言编写已知二叉树采用二叉链表存储结构，设计一个算法，使二叉树中所有结点的左右子树相互交换。

以下是该问题的算法实现：

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void swap(struct TreeNode* root) {
    if (root == NULL) return;
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    swap(root->left);
    swap(root->right);
}

解释：从根节点开始遍历每个节点，对于每个节点，交换其左右子树。然后递归地对其左右子节点执行相同的操作。最终，整棵二叉树中的每个节点的左右子树都被交换。