G、智乃的树旋转(easy version)

还是题解就写在了题目当中。

认真读题，注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变

所以二重循环枚节点，当发现在两颗树中某一对节点互为父子关系时，直接输出原本是父亲的节点。

如果不存在这么一个节点，说明不用旋转，输出0即可。

时间复杂度$O(N^2)O(N^2)$，空间复杂度$O(1)O(1)$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct tree
{
    int fa;
    int ch[2];
} t[MAXN], a[MAXN];
int input_tree(tree* t, int n)
{
    int x, y;
    std::vector<bool> v(n + 1, true);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &x, &y);
        v[x] = v[y] = false;
        t[i].ch[0] = x;
        t[i].ch[1] = y;
        if (x)t[x].fa = i;
        if (y)t[y].fa = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (v[i])return i;
    }
    return -1;
}
int n, root_a, root_t;
vector<int>vv;
int main()
{
    scanf("%d", &n);
    root_a = input_tree(a, n);
    root_t = input_tree(t, n);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(t[i].fa==j&&a[j].fa==i)
            {
                printf("1\n%d\n",i);
                return 0;
            }
        }
    }
    printf("0\n");
}