https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked
心血来潮，突然感觉很久没做leetcode，刷一题。
看到“简单”，哦吼，应该很快吧。
结果真是《简单》
题目描述
给你一个树，判断这个树是否根据根节点做中轴线是对称的。
思路
层级遍历
我的第一反应是，简单～
感觉不是层级遍历一下，得到一层信息之后，把他们拿出来，只要这个一层拿出来的序列是对称的，每一层都是对称的，就说明这个树就是对称的。
于是乎我就开始编码，写写写遇到第一个问题：
我该如何明确这一层已经结束了呢？
“聪明”的我觉得不是直接计数一下就完事了吗？第一层1，第二层2，第三层2*2…
但这个又个前提是，满二叉树才能够使用。“简单”～只要看到null进行填充就好啦～
于是我就开开心心写代码，提交然后WA笑死。
问题：因为如果使用层级遍历，并且填充的话，理论上是可以的，但是我用的层级遍历是使用队列进行遍历的。这就有一个问题
当你的第一层也就是2，2在queue里面的时候，这时候没问题，可以进行填充知道第二层应该是[nil, 2, 2, nil]，并且也插入了队列[2,2]。
但是我当时写的逻辑是，我只要判断[nil, 2, 2, nil]这个成立之后就不管了，直接flush掉，这时候就有个问题，我怎么知道队列中的[2,2]是那个？？他是左树的还是右树的还是混的？
而且就算我保留了上一层的结果，我是可以判断他在那个，但感觉逻辑会很混乱，而且遇上这种全部数值一致的感觉没法做。
但我在写这个博客时候，感觉可以将树展开成数组保存的那种方式，应该就可以了。这样就可以保证每一个nil都是正确填充。但感觉会非常占内存。。。
中序遍历
前面层级遍历不行之后，我就换了思路，感觉不是中序一下，这个树只要这个树是对称的理论上来说
[左树]中[右树]
这里的左树reverse一下会等于右树
感觉这个思路一点问题没有，直接写代码，哈哈哈又是WA
问题：
看这个图，你会发现这里并不对称，但左子树，右子树无论前中后序全部都一样都是[2,2]
因为
题目要求对称，本质上是要获取树的形状信息，但是你如果用了中序遍历，就会使得树的形状信息被压缩了，压缩成了序列信息。
这里是有损的。
而一个单纯的序列信息并不能准确对应一个树，因为都知道，想要还原一个树，你必须要有中序遍历和其他任何一种便利，所以你现在只有中序遍历，是不能够判断是否对称的。
同步中序
基于上面思路，我的脑子开始抽象了起来，我感觉我不能直接中序一下压缩，然后用压缩后的结果判断，那我就让左树跟右树一起同步做“中序遍历”，这样在做同步的过程之中进行判断，保证树的形状信息。
通俗一点讲就是，左树要往左边走，右树遍历也往左边走。
但是是要判断对称的，所以左树往左边走，右树就往右边走。
然后就有了以下代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func judge(node1 *TreeNode, node2 *TreeNode) bool {
if (node1 != nil && node2 == nil) || (node1 == nil && node2 != nil) {
return false
}
return true
}
func query(node1 *TreeNode, node2 *TreeNode) bool{
if !judge(node1, node2){
return false
}
if node1 == nil{
return true
}
if !query(node1.Left, node2.Right) {
return false
}
if node1.Val != node2.Val{
return false
}
if !query(node1.Right, node2.Left) {
return false
}
return true
}
func isSymmetric(root *TreeNode) bool {
// left := make([]int, 0)
// left = midQuery(root.Left, left)
// right := make([]int, 0)
// right = midQuery(root.Right, right)
// fmt.Println(left, right)
// if len(left) != len(right){
// return false
// }
// for i := 0; i < len(left); i ++ {
// if left[i] != right[len(left)-1 - i] {
// return false
// }
// }
if !judge(root.Left, root.Right) {
return false
}
return query(root.Left, root.Right)
}
真tmd简单啊～