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

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

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

#define MAX_SIZE 100

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义栈结构体
typedef struct Stack {
    TreeNode *data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

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

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

// 入栈
void push(Stack *s, TreeNode *node) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++s->top] = node;
}

// 出栈
TreeNode *pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return NULL;
    }
    return s->data[s->top--];
}

// 获取栈顶元素
TreeNode *getTop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return NULL;
    }
    return s->data[s->top];
}

// 判断节点是否在二叉树中
int isNodeInTree(TreeNode *root, TreeNode *node) {
    if (root == NULL) {
        return 0;
    }
    if (root == node) {
        return 1;
    }
    return isNodeInTree(root->left, node) || isNodeInTree(root->right, node);
}

// 查找任意两个树中节点的最近公共祖先
TreeNode *lowestCommonAncestor(TreeNode *root1, TreeNode *root2, TreeNode *p, TreeNode *q) {
    // 定义两个栈，用于存储从根节点到节点p和节点q的路径
    Stack stack1, stack2;
    initStack(&stack1);
    initStack(&stack2);
    // 从根节点开始遍历两棵树，分别找到节点p和节点q，并将路径存储到对应的栈中
    TreeNode *cur1 = root1;
    while (cur1 || !isEmpty(&stack1)) {
        while (cur1) {
            push(&stack1, cur1);
            if (cur1 == p || cur1 == q) {
                break;
            }
            cur1 = cur1->left;
        }
        cur1 = getTop(&stack1);
        if (cur1->right && cur1->right != pop(&stack1)) {
            cur1 = cur1->right;
        } else {
            if (cur1 == p || cur1 == q) {
                break;
            }
            cur1 = NULL;
        }
    }
    TreeNode *cur2 = root2;
    while (cur2 || !isEmpty(&stack2)) {
        while (cur2) {
            push(&stack2, cur2);
            if (cur2 == p || cur2 == q) {
                break;
            }
            cur2 = cur2->left;
        }
        cur2 = getTop(&stack2);
        if (cur2->right && cur2->right != pop(&stack2)) {
            cur2 = cur2->right;
        } else {
            if (cur2 == p || cur2 == q) {
                break;
            }
            cur2 = NULL;
        }
    }
    // 如果节点p或节点q不在任何一棵树中，则它们没有公共祖先
    if (!isNodeInTree(root1, p) || !isNodeInTree(root1, q) || !isNodeInTree(root2, p) || !isNodeInTree(root2, q)) {
        return NULL;
    }
    // 从栈顶开始比较两个栈中的元素，找到最后一个相同的节点即为最近公共祖先
    TreeNode *ancestor = NULL;
    while (!isEmpty(&stack1) && !isEmpty(&stack2)) {
        TreeNode *node1 = pop(&stack1);
        TreeNode *node2 = pop(&stack2);
        if (node1 == node2) {
            ancestor = node1;
        } else {
            break;
        }
    }
    return ancestor;
}

// 创建二叉树
TreeNode *createBinaryTree(int arr[], int index, int n) {
    if (index >= n || arr[index] == -1) {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = arr[index];
    root->left = createBinaryTree(arr, 2 * index + 1, n);
    root->right = createBinaryTree(arr, 2 * index + 2, n);
    return root;
}

int main() {
    // 测试数据
    int arr1[] = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
    int arr2[] = {5, 6, 2, -1, -1, 7, 4};
    TreeNode *root1 = createBinaryTree(arr1, 0, sizeof(arr1) / sizeof(arr1[0]));
    TreeNode *root2 = createBinaryTree(arr2, 0, sizeof(arr2) / sizeof(arr2[0]));
    TreeNode *p = root1->left;
    TreeNode *q = root2->left->right;
    // 查找任意两个树中节点的最近公共祖先
    TreeNode *ancestor = lowestCommonAncestor(root1, root2, p, q);
    if (ancestor != NULL) {
        printf("The lowest common ancestor of node %d and node %d is %d.\n", p->val, q->val, ancestor->val);
    } else {
        printf("Node %d and node %d have no common ancestor.\n", p->val, q->val);
    }
    return 0;
}