7-29 二叉搜索树的最近公共祖先 分数 30 作者 陈越 单位 浙江大学 给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。 输入格式： 输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。 输出格式： 对每一对给定的 U 和 V，如果找到 A 是它们的最近公共祖先结点的键值，则在一行中输出 LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 X is an ancestor of Y.，其中 X 是那个祖先结点的键值，Y 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 ERROR: U is not found. 或者 ERROR: V is not found.，或者 ERROR: U and V are not found.。 输入样例： 6 8 6 3 1 2 5 4 8 7 2 5 8 7 1 9 12 -3 0 8 99 99 输出样例： LCA of 2 and 5 is 3. 8 is an ancestor of 7. ERROR: 9 is not found. ERROR: 12 and -3 are not found. ERROR: 0 is not found. ERROR: 99 and 99 are not found. 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB 栈限制 8192 KB 用c语言

<think> 题目要求根据二叉搜索树的先序遍历序列，处理多组查询，找出两个节点的最近公共祖先（LCA）。二叉搜索树的特点是：对于任意节点，其左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。 解题思路： 1. 根据先序遍历序列重建二叉搜索树。由于是先序遍历，第一个元素是根节点，然后接下来的序列中，连续小于根节点的部分为左子树，大于根节点的部分为右子树。 2. 建立二叉树：使用递归方法构建二叉搜索树。 3. 对于每一组查询（U, V）： a. 检查U和V是否在树中。我们可以通过遍历树（或者利用二叉搜索树特性查找）来检查。如果有一个不存在，则输出相应的错误信息。 b. 如果都存在，则寻找LCA。在二叉搜索树中，LCA的特点是：其值介于U和V之间（包括等于其中之一）。具体方法： - 从根节点开始遍历，如果当前节点的值大于U和V，则LCA在左子树； - 如果当前节点的值小于U和V，则LCA在右子树； - 否则，当前节点就是LCA（即U和V分别位于当前节点的左右子树中，或者其中一个等于当前节点）。 c. 注意特殊情况：如果U和V中的一个是另一个的祖先，那么在找到LCA时，这个祖先节点就是LCA，但根据题目要求，需要输出“X is an ancestor of Y.”。实际上，在二叉搜索树中，如果U是V的祖先，那么从根到V的路径上会经过U。我们在查找LCA的过程中，会遇到U（或V）节点，此时该节点就是祖先。 但是，我们需要注意的是：题目要求如果其中一个节点是另一个节点的祖先，则输出祖先关系。所以，在寻找LCA的过程中，我们可以同时判断是否在路径上出现了U或V。 然而，有一个更直接的方法：在查找LCA之前，我们可以先记录从根节点到U和到V的路径，然后比较这两条路径，最后一个相同的节点就是LCA。同时，在路径中，如果U出现在V的路径上，那么U就是V的祖先，同理V也可能是U的祖先。 由于二叉搜索树的特性，我们可以不用显式存储路径，而是边遍历边比较，但为了清晰，我们可以分别存储路径。 步骤： 1. 建树：根据先序遍历序列递归构建二叉搜索树。 2. 实现一个查找函数，用于查找节点并记录路径（或者判断是否存在）。 3. 对于每组查询： - 先检查两个节点是否存在。 - 如果都存在，分别获取从根节点到U和到V的路径。 - 然后比较两条路径，找到最后一个相同的节点，即为LCA。 - 然后判断这个LCA是不是U或V：如果LCA等于U，则U是V的祖先；如果LCA等于V，则V是U的祖先；否则，输出LCA。 但是，题目要求输出的格式有三种情况，我们需要仔细判断。 另一种方法是利用二叉搜索树的特性直接查找LCA（不需要显式存储整个路径）： while (root != NULL) { if (root->val > u && root->val > v) root = root->left; else if (root->val < u && root->val < v) root = root->right; else break; } // 此时的root就是LCA 然后，我们需要判断U和V中是否有一个是另一个的祖先。注意：在二叉搜索树中，如果一个节点是另一个节点的祖先，那么它一定在另一个节点的路径上。但是，我们上面找到的LCA，如果LCA等于U（或V），那么U（或V）就是另一个节点的祖先；否则，就是普通的LCA。 所以，我们可以这样做： Step1: 检查U和V的存在性（必须各自存在）。 Step2: 用上述循环找到LCA（注意这个循环的前提是U和V都存在）。 Step3: 然后分别检查： 如果LCA的值等于U，则输出“U is an ancestor of V.”（注意：这里U是祖先，V是后代，但要注意也可能V等于U，但题目中键值不同？注意题目没有说不同，所以可能相同）。但是，题目中给出的是不同的整数，但在查询时，可能查询相同的节点？注意输入样例最后有“99 99”，所以两个键值可能相同。 注意：题目中说明“所有键值都在整型int范围内”，但没有说节点值互不相同？但是输入描述“随后一行给出 N 个不同的整数”，所以节点值互不相同。查询的键值对可能是相同的，比如两个99。 对于键值相同的情况（即U等于V）： - 如果这个值在树中，那么它们的LCA就是它们自己，因此输出“U is an ancestor of V.”实际上也是正确的？但是注意，这里U和V代表同一个节点，所以应该说“U is an ancestor of V.”（但自己也是自己的祖先？题目没有明确，但输入样例输出“ERROR: 99 and 99 are not found.”）。为什么输出这个？因为题目要求：如果二叉搜索树中找不到以 U 或 V 为键值的结点，则输出错误信息。注意这里两个都是99，如果树中没有99，那么两个都没找到。 因此，对于相同键值的处理： - 如果U等于V，那么需要检查这个值是否在树中： * 如果在树中，那么按照祖先关系，我们可以说“U is an ancestor of V.”（因为从根到该节点，U（V）出现在路径上，所以是另一个的祖先？但这里两个相同，所以可以说自己就是自己的祖先？） * 但是，题目输入样例中，对于99 99，输出的是“ERROR: 99 and 99 are not found.”，因为树中没有99。 所以，我们需要先分别判断U和V是否在树中，即使U等于V，也要判断一次（如果不在，则两个都没找到）。 具体步骤： 1. 建树：根据先序序列构建二叉搜索树。 2. 对于每组查询： a. 判断U是否在树中，V是否在树中。 b. 如果有一个不存在： 如果U不在且V不在，且U和V相等，输出“ERROR: U and V are not found.”（题目样例的输出：ERROR: 99 and 99 are not found.） 如果U不在，V在，则输出“ERROR: U is not found.”（注意：如果V也不在，但是题目要求：如果U或V有一个不在，就输出对应的错误，但这里两者都不在，按照样例，会输出两个都找不到？注意样例输入中有一组“12 -3”输出“ERROR: 12 and -3 are not found.”，另一组“0 8”输出“ERROR: 0 is not found.”（这里8是存在的，但0不存在）。所以规则是： - 如果U不在树中，而V在树中，输出“ERROR: U is not found.” - 如果V不在树中，而U在树中，输出“ERROR: V is not found.” - 如果U和V都不在树中，输出“ERROR: U and V are not found.” c. 如果都在树中： 用二叉搜索树的性质寻找LCA：从根节点开始，如果当前节点值大于U和V，则进入左子树；如果小于U和V，则进入右子树；否则当前节点就是LCA。 然后判断： 如果LCA的值等于U，那么输出“U is an ancestor of V.” 如果LCA的值等于V，那么输出“V is an ancestor of U.” 否则，输出“LCA of U and V is LCA.” 注意：这里有一个细节，在寻找LCA的过程中，我们并不需要知道路径，因为二叉搜索树的性质可以直接定位。但是，我们要注意：在二叉搜索树中，如果U是V的祖先，那么U一定在从根到V的路径上，所以当我们在寻找LCA时，如果当前节点等于U（或V），那么就会停止，因为当前节点（U）的值满足：它在U和V之间（因为U等于当前节点，而V可能在它的左或右子树，或者等于它？但V不可能等于它，因为节点值互不相同）。所以，当LCA等于U时，说明U就是V的祖先（因为U在V的路径上，并且V在U的子树中）。 但是，还有一种情况：U和V可能不在同一个子树中？不会，因为二叉搜索树的性质，如果U小于V，那么U在左子树，V在右子树，那么LCA就是根节点（不一定是根，但一定大于U小于V，或者介于两者之间）。 因此，上述方法是正确的。 算法步骤总结： 1. 构建二叉搜索树（根据先序遍历序列）。 2. 对于每组查询： a. 分别检查U和V是否存在（写一个查找函数）。 b. 若存在性有问题，按规则输出错误。 c. 若都存在： - 设置当前节点cur为根节点。 - 在cur不为空的情况下循环： 如果cur的值大于U和V，则cur指向左孩子； 如果cur的值小于U和V，则cur指向右孩子； 否则，跳出循环（此时cur就是LCA）。 - 判断cur的值： 如果等于U，则输出“U is an ancestor of V.” 如果等于V，则输出“V is an ancestor of U.” 否则，输出“LCA of U and V is cur->val.” 但是，这里有一个问题：循环跳出时的cur节点，它的值是否一定在U和V之间？不一定，因为可能等于U或V。实际上，跳出条件就是当前节点的值介于U和V之间（包括等于其中之一）。所以正确。 然而，我们需要考虑U和V的大小关系？不需要，因为我们可以通过比较大小来移动，但是我们的循环条件中，如果当前节点大于两者，则往左；小于两者，则往右；否则（即当前节点介于两者之间，或者等于其中之一）就跳出。所以不用事先确定U和V的大小。 注意：有可能U和V的大小关系不确定（比如U>V），但我们的循环条件中，我们使用的是当前节点同时大于U和V，或者同时小于U和V，否则就跳出。所以不管U和V谁大谁小，只要当前节点不满足同时大于或同时小于，就跳出。而介于两者之间（包括等于）就是我们要的LCA。 例子：U=2, V=5（或者U=5, V=2）都没有关系，因为循环条件中，如果当前节点是3，那么3大于2且大于5？不对，3大于2但小于5？所以不满足同时大于或同时小于，所以跳出。此时3介于2和5之间，所以3是LCA。 所以，代码实现如下： 步骤： 1. 构建二叉搜索树节点结构。 2. 根据先序序列递归建树（或者迭代建树，因为递归深度可能达到10000，可能会栈溢出？题目要求栈限制8192KB，而递归深度10000，每个函数调用约几十字节，10000*40=400KB，所以递归可以接受）。 3. 实现查找函数：在树中查找一个值是否存在。 4. 处理M组查询。 递归建树函数： TreeNode* build(int *pre, int start, int end) { if (start > end) return NULL; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = pre[start]; int i; for (i=start+1; i<=end; i++) { if (pre[i] > pre[start]) break; } root->left = build(pre, start+1, i-1); root->right = build(pre, i, end); return root; } 但是，这样每次都要扫描，时间复杂度O(n^2)。题目中N最大10000，最坏情况（链状）递归深度10000，而且扫描的总次数是O(n^2)，最大可能达到10^8，可能超时（时间限制200ms）。所以需要优化建树。 我们可以用迭代法，使用栈来建树，或者用单调栈。但还有一种简单方法：利用二叉搜索树的性质，通过设置上下界递归建树，不需要扫描，只需记录索引。 另一种递归建树（使用索引和上下界）： TreeNode* build(int *pre, int *index, int min, int max, int size) { if (*index >= size) return NULL; int val = pre[*index]; if (val < min || val > max) return NULL; // 如果当前值不在范围内，则不能作为该子树根节点 TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = val; (*index)++; root->left = build(pre, index, min, val-1, size); // 左子树范围[min, val-1] root->right = build(pre, index, val+1, max, size); // 右子树范围[val+1, max] return root; } 调用方式：int index = 0; root = build(pre, &index, INT_MIN, INT_MAX, N); 但是，这种方法不需要扫描，每个节点访问一次，时间复杂度O(n)。 注意：上下界用INT_MIN和INT_MAX（需要包含limits.h）。 但是，题目中说键值是int范围内，所以可以用这种方法。 因此，我们采用这种方法建树。 数据结构定义： typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; 然后，我们需要一个查找函数： bool find(TreeNode *root, int key) { if (root == NULL) return false; if (root->val == key) return true; else if (key < root->val) return find(root->left, key); else return find(root->right, key); } 或者使用非递归以节省栈空间（但N=10000，递归深度可能很深，最坏情况10000，栈可能会溢出？题目栈限制8192KB，每个递归调用大约几十字节，10000*40=400KB，所以递归不会溢出）。 但是，为了避免递归深度太深，我们可以用非递归查找。 然而，题目要求用C语言，我们按上述思路编写代码。 注意：在寻找LCA时，我们使用非递归循环（以避免递归深度）。 代码结构： #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <stdbool.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 递归建树（使用上下界） TreeNode* buildTree(int pre[], int* index, int min, int max, int n) { if (*index >= n) return NULL; int val = pre[*index]; if (val < min || val > max) return NULL; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = val; (*index)++; root->left = buildTree(pre, index, min, val-1, n); root->right = buildTree(pre, index, val+1, max, n); return root; } // 查找节点是否存在（递归） bool find(TreeNode* root, int key) { if (root == NULL) return false; if (root->val == key) return true; if (key < root->val) return find(root->left, key); else return find(root->right, key); } // 寻找LCA（非递归） TreeNode* findLCA(TreeNode* root, int u, int v) { TreeNode* cur = root; while (cur) { if (cur->val > u && cur->val > v) cur = cur->left; else if (cur->val < u && cur->val < v) cur = cur->right; else break; } return cur; } int main() { int M, N; scanf("%d %d", &M, &N); int preorder[N]; for (int i = 0; i < N; i++) scanf("%d", &preorder[i]); int index = 0; TreeNode* root = buildTree(preorder, &index, INT_MIN, INT_MAX, N); for (int i = 0; i < M; i++) { int u, v; scanf("%d %d", &u, &v); bool existU = find(root, u); bool existV = find(root, v); if (!existU && !existV) printf("ERROR: %d and %d are not found.\n", u, v); else if (!existU) printf("ERROR: %d is not found.\n", u); else if (!existV) printf("ERROR: %d is not found.\n", v); else { TreeNode* lca = findLCA(root, u, v); // 注意：这里lca不可能为NULL，因为u和v都存在 if (lca->val == u) printf("%d is an ancestor of %d.\n", u, v); else if (lca->val == v) printf("%d is an ancestor of %d.\n", v, u); else printf("LCA of %d and %d is %d.\n", u, v, lca->val); } } // 释放二叉树（省略，因为题目不需要） return 0; } 但是，有一个边界问题：在buildTree函数中，如果当前值不在[min, max]范围内，则返回NULL。这样，在构建过程中，如果当前节点不符合范围，则不会构建，并且index不会增加，这样会导致死循环？所以我们需要确保先序遍历序列是合法的二叉搜索树。 如何构建：我们按顺序使用先序遍历序列，第一个节点是根，然后递归构建左子树（在[min, val-1]范围内）和右子树（[val+1, max]范围内）。如果当前节点不在范围内，则返回NULL，并且index保持不变，这样在回溯后，父节点会尝试将其作为右子树（对于左子树构建时，如果某个节点不在左子树范围内，则返回NULL，然后父节点会继续用这个节点去构建右子树？不对，因为我们先构建左子树，然后构建右子树。但是，在左子树构建时，如果当前节点不在左子树的范围[min, val-1]内，那么就不会被构建，然后返回到父节点，父节点继续构建右子树（使用同一个index）？这样会导致右子树使用了这个节点。但是，这个节点应该是右子树的节点，所以这样是合理的。 然而，这样会导致一个问题：我们在构建左子树时，如果遇到一个不在左子树范围内的节点，我们就返回NULL，然后这个节点会被父节点用于构建右子树吗？在buildTree函数中，我们先尝试构建左子树，然后构建右子树。但是，在构建左子树时，我们传入的是当前的index（指针），如果构建左子树时消耗了一些节点，那么构建右子树时index已经增加了。但是，如果某个节点在左子树构建时被跳过（因为不在左子树范围），那么它不会被消耗，然后构建右子树时会重新尝试这个节点（因为index没有增加）。 所以，这个构建函数是正确的。 但是，我们也可以不用上下界，而用先序序列和中序序列？题目只给了先序，而二叉搜索树的中序是排序的，所以我们可以先排序，然后利用先序和中序建树。但这样时间复杂度O(nlogn)建树，也可以接受。但上述方法更直接。 测试样例： 先序序列：6 3 1 2 5 4 8 7 查询：2 5 -> LCA=3，输出正确。 但是，我们还需要注意：建树过程中index的变化。例如，构建根节点6，然后index=1，构建左子树（范围INT_MIN到5），下一个节点3（在INT_MIN~5内），然后构建3的左子树（范围INT_MIN~2），节点1（符合），然后构建1的左子树（没有，因为下一个是2，但2大于1（1的左子树范围INT_MIN~0），所以1的左子树为NULL，然后构建1的右子树（范围2~2），节点2（符合），所以2成为1的右孩子。然后回到3，构建3的右子树（范围4~5），下一个节点5（符合），然后构建5的左子树（范围4~4），节点4（符合）作为5的左孩子。然后右子树为空。然后回到6，构建右子树（范围7~INT_MAX），节点8（符合），然后构建8的左子树（范围7~7），节点7（符合）作为左孩子。 所以树的结构正确。 但是，我们需要注意递归建树时，index是全局递增的，所以不会重复使用节点。 因此，代码实现如下（注意细节）： 修正：在buildTree函数中，如果当前节点不符合范围，我们应该直接返回NULL，并且不消耗这个节点（即index不增加）。这样，父节点会尝试把这个节点用于右子树。 但是，在函数中，我们是在创建根节点之前判断的，如果不符合范围，我们返回NULL，并且index保持不变。这样，当父节点调用时，这个节点还会被保留，然后父节点会尝试用这个节点构建右子树（在左子树构建之后）。 所以，代码正确。 但是，要注意index是全局递增的，所以我们在构建左子树的时候，如果消耗了节点，index会增加，然后构建右子树时，从新的index开始。 因此，我们不需要改变。 但是，在构建左子树时，我们传入当前的index，左子树构建完成后，index已经指向了左子树后面的节点，然后构建右子树时，从当前index开始。 所以，整个过程是先序的。 最后，我们还需要注意内存泄漏问题（题目没有要求，但为了规范，我们可以释放，但题目结束程序就终止，所以可以不考虑）。 代码优化：查找函数使用非递归以避免递归深度过大（虽然不会溢出，但可以减少栈空间使用）。 非递归查找： bool find(TreeNode* root, int key) { TreeNode* cur = root; while (cur) { if (cur->val == key) return true; else if (key < cur->val) cur = cur->left; else cur = cur->right; } return false; } 修改查找函数为非递归。 另外，寻找LCA的函数已经是非递归。 所以，最终代码如下： 注意：题目输入中的键值可能是负数，所以上下界用INT_MIN和INT_MAX。 由于键值在int范围内，所以使用INT_MIN和INT_MAX是安全的。 我们开始编写代码，并注意格式要求。 注意：输出格式要严格按照题目要求（空格、大小写、标点等）。 </think> ### 二叉搜索树最近公共祖先（C语言实现） ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <limits.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 构建二叉搜索树（递归） TreeNode* buildTree(int preorder[], int* index, int min, int max, int n) { if (*index >= n) return NULL; int value = preorder[*index]; // 检查当前值是否在合法范围内 if (value < min || value > max) return NULL; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = value; (*index)++; // 递归构建子树 root->left = buildTree(preorder, index, min, value - 1, n); root->right = buildTree(preorder, index, value + 1, max, n); return root; } // 检查节点是否存在（非递归） bool nodeExists(TreeNode* root, int key) { TreeNode* cur = root; while (cur) { if (cur->val == key) return true; cur = (key < cur->val) ? cur->left : cur->right; } return false; } // 查找最近公共祖先（非递归） TreeNode* findLCA(TreeNode* root, int u, int v) { TreeNode* cur = root; while (cur) { if (cur->val > u && cur->val > v) cur = cur->left; else if (cur->val < u && cur->val < v) cur = cur->right; else break; } return cur; } int main() { int M, N; scanf("%d %d", &M, &N); int preorder[N]; for (int i = 0; i < N; i++) { scanf("%d", &preorder[i]); } int index = 0; TreeNode* root = buildTree(preorder, &index, INT_MIN, INT_MAX, N); while (M--) { int u, v; scanf("%d %d", &u, &v); bool u_exists = nodeExists(root, u); bool v_exists = nodeExists(root, v); if (!u_exists && !v_exists) { printf("ERROR: %d and %d are not found.\n", u, v); } else if (!u_exists) { printf("ERROR: %d is not found.\n", u); } else if (!v_exists) { printf("ERROR: %d is not found.\n", v); } else { TreeNode* lca = findLCA(root, u, v); if (lca->val == u) { printf("%d is an ancestor of %d.\n", u, v); } else if (lca->val == v) { printf("%d is an ancestor of %d.\n", v, u); } else { printf("LCA of %d and %d is %d.\n", u, v, lca->val); } } } return 0; } ``` ### 代码说明 1. **二叉搜索树构建** - 使用递归方法根据先序序列构建BST - 利用`INT_MIN`和`INT_MAX`作为初始范围边界 - 时间复杂度：O(N) 2. **节点存在性检查** - 非递归实现，避免栈溢出风险 - 利用BST特性高效查找 - 时间复杂度：O(log N) 3. **LCA查找算法** - 基于BST特性：LCA是第一个值介于u和v之间的节点 - 非递归实现，空间复杂度O(1) - 时间复杂度：O(log N) 4. **输入/输出处理** - 严格遵循题目要求的输出格式 - 正确处理多种错误情况 - 高效处理最大规模数据（N≤10000）