一流的聊城做网站费用,天津网架公司,无锡朝阳网站建设,wordpress如何关闭网页https://leetcode.cn/problems/symmetric-tree/description/?envTypestudy-plan-v2envIdtop-100-liked
心血来潮#xff0c;突然感觉很久没做leetcode#xff0c;刷一题。 看到“简单”#xff0c;哦吼#xff0c;应该很快吧。 结果真是《简单》
题目描述
给你一个…https://leetcode.cn/problems/symmetric-tree/description/?envTypestudy-plan-v2envIdtop-100-liked
心血来潮突然感觉很久没做leetcode刷一题。 看到“简单”哦吼应该很快吧。 结果真是《简单》
题目描述
给你一个树判断这个树是否根据根节点做中轴线是对称的。
思路
层级遍历
我的第一反应是简单 感觉不是层级遍历一下得到一层信息之后把他们拿出来只要这个一层拿出来的序列是对称的每一层都是对称的就说明这个树就是对称的。 于是乎我就开始编码写写写遇到第一个问题 我该如何明确这一层已经结束了呢 “聪明”的我觉得不是直接计数一下就完事了吗第一层1第二层2第三层2*2… 但这个又个前提是满二叉树才能够使用。“简单”只要看到null进行填充就好啦 于是我就开开心心写代码提交然后WA笑死。
问题因为如果使用层级遍历并且填充的话理论上是可以的但是我用的层级遍历是使用队列进行遍历的。这就有一个问题 当你的第一层也就是22在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简单啊
