P5018 [NOIP2018 普及组] 对称二叉树_noip2018对称二叉树 时间复杂度

难度：４
知识点：二叉树

题意：给你一个二叉树，让你找这个二叉树里面节点数最多的对称子树，这道题我看题解有O(n)的做法，不会，然后我这个是用的最简单的暴力法，递归判断，用的先序，只要当前点为节点的子树是对称的话，那么就没有必要往下判断了，然后就是怎么判断一个树是不是对称的，我们可以把这个问题转化为判断两个树是不是一样的，第二个树就是第一个树所有左右儿子颠倒之后得到的树，如果这两个树一样，那就说明第一个树是对称的，

遍历最好采用先序遍历，这样如果当前节点为根的子树是对称的话，那么就不用往下判断了，可以及时去掉不可能的情况，判断函数的逻辑也比较简单，都空返回是，其中有一个不空返回否，能进行到这里说明都不空了，可以累加节点数了，后面记录答案使用，然后是节点的权值不等，返回否，进行到这里，节点的权值也相等了，就递归判断两个树的两个子节点即可

总之，这个就是最简单最暴力的方法，但是过这道题也是绰绰有余了，

总结，学习了如何判断一个二叉树是不是对称的，

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) x.size())
#define all(x)
1
2
3
4
5
6