11231: 【原1231】lca

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1231

Description

P332.3

Input Format

第一行输入三个整数 N X Y，表示树节点个数为N

第二行到第N+1行，每行两个整数A 和 B，表示编号为k的节点的左右孩子的编号为A和B

其中，节点编号是从1开始的，A或者B是0表示没有对应的孩子

Output Format

输出节点X和节点Y的最近公共祖先的编号

Sample Input

Sample Output

样例解释

            1
           / \
          /   \
         2     3
        / \   / \
       4!  5 6!  7

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "queue"
#include "cmath"
#include "stack"
#include "cstring"
using namespace std;

//二叉树类
template <class T>
class myBinaryTree {
public:
    class node {
    public:
        T data;
        node* lchild = nullptr, * rchild = nullptr, * parent = nullptr;
    };
    node* root = nullptr;
    node** nodeList = nullptr;
    long long sizeOfTree = 0;

    //创建一个相应大小的树
    void createTree(int num) {
        nodeList = new node * [num + 1]{ nullptr };
        sizeOfTree = num;
    }
    //创建结点（全部完成后需要CheckRoot进行根节点识别）
    void createNode(int nodeNum, int lchild, int rchild, T data) {
        if (nodeList[nodeNum] == nullptr)
            nodeList[nodeNum] = new node;

        nodeList[nodeNum]->data = data;

        if (lchild != 0) {
            if (nodeList[lchild] == nullptr)
                nodeList[lchild] = new node;
            nodeList[lchild]->parent = nodeList[nodeNum];
            nodeList[nodeNum]->lchild = nodeList[lchild];
        }

        if (rchild != 0) {
            if (nodeList[rchild] == nullptr)
                nodeList[rchild] = new node;
            nodeList[rchild]->parent = nodeList[nodeNum];
            nodeList[nodeNum]->rchild = nodeList[rchild];
        }
    }
    //创建一个num大小的树，数据为treeData
    void createTree(T * treeData, int num) {
        createTree(num);
        for (int i = 1; i <= num; i++) {
            int lchild = i * 2 <= num ? i * 2 : 0,
                rchild = i * 2 + 1 <= num ? i * 2 + 1 : 0;
            createNode(i, lchild, rchild, treeData[i - 1]);
        }
        checkRoot();
    }

    void checkRoot() {
        for (int i = 1; i <= sizeOfTree; i++) {
            if (nodeList[i]->parent == nullptr) {
                root = nodeList[i];
                break;
            }
        }
    }

    //清空
    void clear() {
        clear(root);
    }

    void clear(node * p) {
        if (p == nullptr)
            return;
        clear(p->lchild);
        clear(p->rchild);
        delete p;
        p = nullptr;
    }

    //构造
    myBinaryTree() {}

    //析构
    ~myBinaryTree() {
        clear(root);
    }

    //判断是否非空
    bool empty() {
        return root == nullptr;
    }

    //返回大小
    long long size() {
        return sizeOfTree;
    }
};

int ans = 0;
//lca(节点)
int lca(myBinaryTree<int>::node* curNode, int d1, int d2) {
    if (curNode == nullptr)
        return 0;
    auto l = lca(curNode->lchild, d1, d2), r = lca(curNode->rchild, d1, d2);
    if (ans > 0)
        return 2;
    else if (l + r + int(curNode->data == d1 || curNode->data == d2) >= 2) {
        ans = curNode->data;
        return 2;
    }
    else
        return l + r + int(curNode->data == d1 || curNode->data == d2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    myBinaryTree<int> bTree;
    int N, X, Y;
    cin >> N >> X >> Y;

    bTree.createTree(N);
    for (int i = 1; i <= N; i++) {
        int lchild, rchild;
        cin >> lchild >> rchild;
        bTree.createNode(i, lchild, rchild, i);
    }
    bTree.checkRoot();
    lca(bTree.root, X, Y);
    cout << ans;

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

int size1 = 0;
long long N, X, Y, Xtemp, Ytemp;
long long father[maxN] = {0}, XFather[maxN] = {0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> X >> Y;
    long long temp1, temp2;

    for (long long i = 1; i <= N; i++) {
        cin >> temp1 >> temp2;
        if (temp1 != 0) {
            father[temp1] = i;
        }
        if (temp2 != 0) {
            father[temp2] = i;
        }
    }

    Xtemp = X;
    Ytemp = Y;
    while (Xtemp != 0) {
        XFather[size1++] = Xtemp;
        Xtemp = father[Xtemp];
    }

    while (Ytemp != 0) {
        for (int i = 0; i < size1; i++) {
            if (XFather[i] == Ytemp) {
                cout << Ytemp << '\n';
                return 0;
            }
        }

        Ytemp = father[Ytemp];
    }

    return 0;
}

yyong119's solution

#include <iostream>
using namespace std;

int N, X, Y;

struct node {
    int left, right, parent;
    node() :left(0), right(0), parent(0) {}
};

node *tree;

class disjointSet {
private:
    int *parent;

public:
    disjointSet(int n) {
        parent = new int[n + 1];
        for (int i = 0; i < n; ++i)parent[i + 1] = -1;
        parent[0] = 0;
    }
    ~disjointSet() {
        delete[]parent;
    }
    int find(int x) {
        if (parent[x]<0)return x;
        return parent[x] = find(parent[x]);
    }
    void merge(int root1, int root2) {
        if (tree[root1].parent == root2) {
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
        else {
            parent[root1] += parent[root2];
            parent[root2] = root1;
        }
    }
};

int LCA(disjointSet& d, node *t, int root) {
    if (!root)return -1;
    int tmp;
    if ((tmp = LCA(d, t, t[root].left)) > 0)return tmp;
    else if ((tmp = LCA(d, t, t[root].right) > 0))return tmp;
    else {
        if (t[root].left)d.merge(root, t[root].left);
        if (t[root].right)d.merge(root, t[root].right);
        if ((tmp = d.find(X)) == d.find(Y))return tmp;
        else return -1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> X >> Y;
    tree = new node[N + 1];
    for (int i = 1; i <= N; ++i) {
        cin >> tree[i].left >> tree[i].right;
        tree[tree[i].left].parent = tree[tree[i].right].parent = i;
    }
    int root = 1;
    while (tree[root].parent)root = tree[root].parent;
    disjointSet d(N);
    cout << LCA(d, tree, root) << endl;
    delete[]tree;
    return 0;
}