LeetCode，Go实现对称二叉树的判别
力扣题目：
给定一个二叉树，检查它是否是镜像对称的。
解题思路
我们先思考下，树对称的条件是什么？
- 对于树的左子树，和右子树，它们的根节点肯定是相同的
- 每个树的左子树必须与另一个树的右子树镜像对称
- 每个树的右子树必须与另一个树的左子树镜像对称
这样就形成了递归问题，对于两个子树，需要判断子树的子树是否对称。注意临界点：如果所给根节点，为空，那么是对称。
程序实现
func isSymmetric(root *TreeNode) bool {
return isMirror(root, root)
}
func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}
复杂度分析
假设树上一共有 n 个节点。
时间复杂度：题目中我们遍历了这棵树，所以渐进时间复杂度为 O(n)。
空间复杂度：递归层数不超过 n，所以渐进空间复杂度为 O(n)。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
