【每日一题】10月19日题目精讲（二叉树）

遍历二叉树，用一个check函数来判断是否是对称二叉树，注意，一旦地下有不是对称二叉树的整个那条树都不是了（刚开始一直理解错题了),用dfs遍历来获得每个父节点的子节点个数，并且统计出来，最后遍历节点，判断函数就可以了。
注意：
需要用到快读，否则会TLE

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int maxn = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
template <class T>//快读
void read(T& x)
{
    char c;
    bool op = 0;
    while (c = getchar(), c < '0' || c > '9')
        if (c == '-')
            op = 1;
    x = c - '0';
    while (c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if (op)
        x = -x;
}
template <class T>
void write(T x)
{
    if (x < 0)
        x = -x, putchar('-');
    if (x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}
///////////////////////////////////////////////////////////
/*struct Edge
{
    int v, w, next;
}edge[maxn];
int tot = 0;
int head[maxn];
inline void Add_edge(int u, int v, int w)//建立邻接表
{
    edge[++tot].next = head[u];
    head[u] = tot;
    edge[tot].v = v;
    edge[tot].w = w;
}*/
///////////////////////////////////////////////////////////
struct Edge {
    int from, to, dist;
};
struct HeadNode {
    int d, u;
    bool operator <(const HeadNode& rhs) const {
        return d < rhs.d;
    }
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int d[maxn];
int p[maxn];
bool done[maxn];
void init(int n) {
    for (int i = 0; i < n; i++)
        G[i].clear();
    edges.clear();
}
void Addedge(int from, int to, int dist) {
    edges.push_back({ from, to, dist });
    m = edges.size();
    G[from].push_back(m - 1);
}
void dijstra(int s) {//dijstra的优先队列优化
    priority_queue<HeadNode> Q;
    for (int i = 0; i < n; i++)
        d[i] = INF;
    d[s] = 0;
    Q.push({ 0,s });
    memset(done, 0, sizeof(done));
    while (!Q.empty()) {
        HeadNode x;
        x = Q.top();
        Q.pop();
        int u = x.u;
        if (done[u])
            continue;
        done[u] = 1;
        for (int i = 0; i < G[u].size(); i++) {
            Edge& e = edges[G[u][i]];
            if (d[e.to] > d[u] + e.dist) {
                d[e.to] = d[u] + e.dist;
                p[e.to] = G[u][i];
                Q.push({ d[e.to],e.to });
            }
        }
    }
}
struct node {
    int val;
    int l, r;
    int size;
}tree[maxn];
bool check(int x, int y) {
    if (x == -1 && y == -1)
        return true;
    if ((x == -1 && y != -1) || (x != -1 && y == -1))
        return false;
    if (tree[x].val != tree[y].val)
        return false;
    if (check(tree[x].l, tree[y].r) && check(tree[x].r, tree[y].l))
        return true;
    return false;
}
void DFS(int v) {
    tree[v].size = 1;//初始化
    if (tree[v].l != -1) {
        DFS(tree[v].l);
        tree[v].size += tree[tree[v].l].size;
    }
    if (tree[v].r != -1) {
        DFS(tree[v].r);
        tree[v].size += tree[tree[v].r].size;
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        read(tree[i].val);
    }
    for (int i = 1; i <= n; i++) {
        read(tree[i].l);
        read(tree[i].r);
    }
    DFS(1);
    int ans = -INF;
    for (int i = 1; i <= n; i++) {
        if (check(tree[i].l, tree[i].r))
            ans = max(ans, tree[i].size);
    }
    cout << ans << endl;
    return 0;
}
/*
10
2 2 5 5 5 5 4 4 2 3
9 10
-1 -1
-1 -1
-1 -1
-1 -1
-1 2
3 4
5 6
-1 -1
7 8
*/