[leetcode100] 101. 对称二叉树

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)
}