题意概括

给定一个二叉树，判断它是否是轴对称的（即自身的镜像）。

输入格式: 输入包含 $N$ 个节点，每个节点用 val left right 的形式描述，其中 left 和 right 是 1-based 的子节点编号，-1 表示空。根节点编号始终为 1。

数据范围:

• $1 \le N \le 1000$ (节点数量)
• $-100 \le val \le 100$ (节点值)

基础知识

判断一棵树是否对称，核心是判断其根节点的左子树和右子树是否互为镜像。这个问题非常适合使用 递归 (Recursion) 或 深度优先搜索 (DFS) 来解决。

我们可以设计一个辅助递归函数，例如 chk(p, q)，用来比较两棵子树（根节点为 p 和 q）是否互为镜像。两棵树互为镜像需要满足以下三个条件：

1. 它们的根节点值相等 (p->val == q->val)。
2. p 的左子树与 q 的右子树互为镜像。
3. p 的右子树与 q 的左子树互为镜像。

递归的终止条件（Base Case）包括：

• 如果两个节点 p 和 q 都是空的 (nullptr 或索引为 -1)，那么它们是镜像的，返回 true。
• 如果其中一个节点为空，另一个不为空，或者它们的值不相等，那么它们不是镜像的，返回 false。

对于整棵树，我们只需要调用 chk(root->left, root->right) 即可。

由于本题的输入是节点信息的列表，我们需要先根据索引关系将树的结构存储起来（例如，使用一个结构体数组），然后再进行递归判断。

该算法的时间复杂度为 $O(N)$，因为我们需要遍历树中的每一个节点一次。空间复杂度为 $O(H)$，其中 $H$ 是树的高度，用于存储递归调用的栈空间。在最坏情况下，$H$ 可以达到 $N$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 定义节点结构体
struct Nde {
    int v, l, r;
};

vector<Nde> t;

// 检查以u和v为根的子树是否互为镜像
bool chk(int u, int v) {
    // 两个都是空节点，是对称的
    if (u == -1 && v == -1) {
        return true;
    }
    // 一个为空一个不为空，或者节点值不同，不对称
    if (u == -1 || v == -1 || t[u].v != t[v].v) {
        return false;
    }

    // 递归检查：u的左子树 vs v的右子树，u的右子树 vs v的左子树
    return chk(t[u].l, t[v].r) && chk(t[u].r, t[v].l);
}

void run() {
    int n;
    cin >> n;

    t.resize(n + 2); // 使用1-based索引，大小设为n+1或n+2
    for (int i = 1; i <= n; ++i) {
        int id = i; // 题目保证节点按顺序给出
        cin >> t[id].v >> t[id].l >> t[id].r;
    }

    if (n == 0) {
        cout << "true" << endl;
        return;
    }

    // 根节点为1，检查其左右子树是否对称
    bool res = chk(t[1].l, t[1].r);

    if (res) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1 (对称):
输入:
7
1 2 2
2 3 4
2 4 3
3 -1 -1
4 -1 -1
输出:
true

样例 2 (不对称):
输入:
4
1 2 2
2 -1 3
2 -1 3
3 -1 -1
输出:
false
*/