利用栈实现任意两个树中节点的最近公共祖先C语言

以下是利用栈实现任意两个树中节点的最近公共祖先的C语言代码：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100 // 栈的最大容量

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

typedef struct Stack {
    TreeNode *data[MAXSIZE];
    int top;
} Stack;

// 创建一个栈
Stack *createStack() {
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    return s;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAXSIZE - 1;
}

// 入栈
void push(Stack *s, TreeNode *node) {
    if (isFull(s)) {
        return;
    }
    s->top++;
    s->data[s->top] = node;
}

// 出栈
TreeNode *pop(Stack *s) {
    if (isEmpty(s)) {
        return NULL;
    }
    TreeNode *node = s->data[s->top];
    s->top--;
    return node;
}

// 求两个节点的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    Stack *s1 = createStack();
    Stack *s2 = createStack();
    TreeNode *node = root, *last = NULL;
    while (node || !isEmpty(s1)) {
        if (node) {
            push(s1, node);
            if (node == p) {
                while (!isEmpty(s2)) {
                    pop(s2);
                }
                for (int i = 0; i <= s1->top; i++) {
                    push(s2, s1->data[i]);
                }
            }
            if (node == q) {
                while (!isEmpty(s1)) {
                    pop(s1);
                }
                for (int i = 0; i <= s2->top; i++) {
                    push(s1, s2->data[i]);
                }
            }
            node = node->left;
        }
        else {
            TreeNode *top = s1->data[s1->top];
            if (top->right && top->right != last) {
                node = top->right;
            }
            else {
                last = pop(s1);
            }
        }
    }
    return s1->data[s1->top];
}

int main() {
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 3;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 5;
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->val = 6;
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->val = 2;
    root->left->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->left->val = 7;
    root->left->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->right->val = 4;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 1;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 0;
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 8;

    TreeNode *p = root->left, *q = root->right;
    TreeNode *ancestor = lowestCommonAncestor(root, p, q);
    printf("The lowest common ancestor of node %d and node %d is node %d.\n", p->val, q->val, ancestor->val);
    return 0;
}

在此代码中，我们利用两个栈`s1`和`s2`分别存储从根节点到两个目标节点的路径。具体实现方法是，从根节点开始遍历树，每当遍历到一个节点时，就将该节点入栈`s1`。如果遍历到了目标节点`p`，则将栈`s2`清空，并将栈`s1`中的所有节点依次出栈并入栈`s2`中。如果遍历到了目标节点`q`，则将栈`s1`清空，并将栈`s2`中的所有节点依次出栈并入栈`s1`中。最终，栈`s1`中的栈顶元素即为两个目标节点的最近公共祖先。