本篇技术文章深入探讨了使用C语言实现寻找二叉树中两个指定节点的最近公共祖先的方法。文中详细解析了算法逻辑，并提供了代码示例，旨在帮助开发者理解与优化相关数据结构操作技巧。
在二叉树中，最低公共祖先（Lowest Common Ancestor, LCA）是指同时是两个给定节点的最近共同祖先。本篇主要介绍如何使用C语言求解二叉树节点的最低公共祖先，并结合ACM题目进行深入解析。
我们考虑最通用的情况：即树不一定是二叉排序树，也不一定有指向父节点的指针。在这种情况下，求解LCA的基本思路是先分别找到两个给定节点到根节点的路径，然后找到这两条路径上的最后一个相同节点，这个节点就是最低公共祖先。
以下是具体实现代码片段：
```c
typedef struct BinaryNode {
int value;
struct BinaryNode *left;
struct BinaryNode *right;
} BinaryNode;
bool GetNodePath(BinaryNode *pRoot, BinaryNode *pNode, vector &v) {
if (pRoot == NULL) return false;
v.push_back(pRoot);
if (pRoot == pNode) return true;
bool found = GetNodePath(pRoot->left, pNode, v);
if (!found) found = GetNodePath(pRoot->right, pNode, v);
if (!found) v.pop_back();
}
BinaryNode* GetCommonParent(BinaryNode *pRoot, BinaryNode *pNode1, BinaryNode *pNode2) {
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL) return NULL;
vector v1, v2;
GetNodePath(pRoot, pNode1, v1);
GetNodePath(pRoot, pNode2, v2);
BinaryNode *pLast = pRoot;
vector::iterator ite1 = v1.begin(), ite2 = v2.begin();
while (ite1 != v1.end() && ite2 != v2.end()) {
if (*ite1 == *ite2) pLast = *ite1;
ite1++;
ite2++;
}
return pLast;
}
```
在ACM题目中，给定一颗树的先序遍历序列和两个节点值，我们需要找出这两个节点的最低公共祖先。这个问题可以通过后序遍历的思想解决，利用栈来保存路径，然后找到两个路径的第一个公共节点。
这里给出一个基于后序遍历思路的C代码示例：
```c
#include
#include
#define N 7000
typedef struct btree {
int val;
struct btree *left;
struct btree *right;
} BTree;
BTree* buildTree(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
if (preStart > preEnd) return NULL;
BTree* node = (BTree*)malloc(sizeof(BTree));
node->val = preorder[preStart];
if (preStart == preEnd) return node;
int inIndex = search(inorder, inStart, inEnd, node->val);
node->left = buildTree(preorder, preStart + 1, preStart + inIndex - inStart, inorder, inStart, inIndex - 1);
node->right = buildTree(preorder, preStart + inIndex - inStart + 1, preEnd, inorder, inIndex + 1, inEnd);
return node;
}
int search(int* inorder, int start, int end, int val) {
for (int i = start; i <= end; i++) {
if (inorder[i] == val)
return i;
}
return -1;
}
BTree* LCA(BTree* root, BTree* n1, BTree* n2) {
stack st;
BTree* lastNode = NULL;
while (root || !st.empty()) {
while (root) {
st.push(root);
root = root->left;
}
root = st.top();
st.pop();
if (root == n1 || root == n2) {
lastNode = root;
} else if (lastNode && (root->left == lastNode || root->right == lastNode)) {
return lastNode;
}
root = root->right;
}
return NULL;
}
int main() {
// 输入处理和调用函数求解LCA
}
```
在样例输入中，我们有两个测试案例。第一个案例中给定的树先序遍历序列是`1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0`，查询两个节点值分别为`6`和`8`，其
5星
