最近公共祖先
Coddy AVL 树：数据结构系列 #10 课程的第 14 课，共 16 课。
两个值的最近公共祖先是指这样一个最深节点：这两个值都位于它的某个子树中。在二叉搜索树中，你不需要直接比较子树，就能找到它：从根节点开始，如果两个值都小于当前节点，答案就在左子树中的某处；如果两个值都大于当前节点，答案就在右子树中。
当两个值分别位于当前节点的两侧，或者其中一个值等于当前节点时，你就找到了分叉点：这个节点就是最近公共祖先。
挑战
简单编写一个函数 lca(tree, p, q)，返回 p 和 q 的最低公共祖先的值。你可以假设这两个值都存在于树中。
亲手试试
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"
int main(void) {
AVLTree* tree = AVLTree_create();
char line1[4096];
fgets(line1, sizeof(line1), stdin);
char* tok = strtok(line1, " \n");
while (tok != NULL) {
AVLTree_insert(tree, atoi(tok));
tok = strtok(NULL, " \n");
}
char line2[256];
fgets(line2, sizeof(line2), stdin);
int p0 = atoi(strtok(line2, " \n"));
int p1 = atoi(strtok(NULL, " \n"));
int result = lca(tree, p0, p1);
printf("%d\n", result);
return 0;
}
AVL 树：数据结构系列 #10中的所有课
自己练习： C 在线编译器