求助

申谭

#include<stdio.h>
using namespace std;
struct node {
    int data;
    node* firstChild;
    node* nextBrother;
};
node* CreateTree()
{
    int k;
    scanf("%d", &k);
    if (k == 0) return NULL;
    node *t = new node;
    t->data = k;
    t->firstChild = CreateTree();
    t->nextBrother = CreateTree();
    return t;
}
void Del(node* root)
{
    if (root == NULL) return;
    node* p = root->firstChild;
    node* next;
    while (p != NULL){
        next = p->nextBrother;
        Del(p);
        p = next;
    }
    delete root;
}

/* 你的代码将出现在这里 */

int main()
{
    int a, b, T;
    scanf("%d", &T);
    while(T--){
        node *root = CreateTree();
        scanf("%d %d", &a, &b);
        printf("%d\n", LeastCommonAncestors(root, a, b));
        Del(root);
    }
    return 0;
}
在本题中你无需编写整个程序，只需实现如下函数
int LeastCommonAncestors(node *root, int a, int b);
这道题只让写目标函数，他把一个树存储成了二叉树，但是寻找祖先的时候要当成普通树去看，该如何进行程序的书写

每个测试点包含多组数据，第1行为一个正整数T，表示数组组数。每组数据为2行，第1行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示。第2行为空格间隔的两个互不相等的整数A和B，表示给定的两个结点值，保证A和B肯定在输入的树中。

注1：我们已知二叉树与其自然对应的树相比，二叉树中结点的左孩子对应树中结点的左孩子，二叉树中结点的右孩子对应树中结点的右兄弟。进而我们可以利用“带空指针信息的先根序列构建二叉树”的方法来构建其对应的树的左孩子-右兄弟存储结构。如8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0对应图1(a)所示的树，1 2 0 3 0 4 0 0 0对应如图1(b)所示的树。

注2：本题中读入数据的操作无需你来完成，而由框架程序完成。

isdkz

1. int LeastCommonAncestors(node *root, int a, int b) {
   
2.     if (root == NULL) return -1; // 如果根节点为空，返回-1表示未找到
   
3.     if (root->data == a || root->data == b) return root->data; // 如果根节点就是a或b，说明找到了其中一个值的祖先
   
4.     int left = LeastCommonAncestors(root->firstChild, a, b); // 在左子树中寻找a和b的祖先
   
5.     int right = LeastCommonAncestors(root->nextBrother, a, b); // 在右兄弟子树中寻找a和b的祖先
   
6.     if (left != -1 && right != -1) return root->data; // 如果a和b分别在左子树和右兄弟子树中找到了祖先，说明当前节点就是最近公共祖先
   
7.     return (left != -1) ? left : right; // 如果只在一个子树中找到了祖先，返回找到的祖先值
   
8. }
   

复制代码

这段代码实现了在普通树的存储结构中寻找两个节点的最近公共祖先。首先判断根节点是否为空或者是否为a或b，如果是则返回根节点的值。然后在左子树和右兄弟子树中分别递归寻找a和b的祖先，最后根据左右子树中找到的祖先情况返回最近公共祖先的值。

申谭

isdkz 发表于 2023-11-22 14:52
这段代码实现了在普通树的存储结构中寻找两个节点的最近公共祖先。首先判断根节点是否为空或者是否为a或b ...

审下题啊，题里给了构建函数的，他记录的是一个二叉树形式，但是他是个树，要按照树的逻辑进行遍历

ba21

申谭 发表于 2023-11-22 16:04
审下题啊，题里给了构建函数的，他记录的是一个二叉树形式，但是他是个树，要按照树的逻辑进行遍历

对机器人说审题。这种回答根本就不用回复，直接把人拉黑。
拉黑，我现在就是这么做的。