使用Go语言判断二叉树是否对称的方法小结
目录
- 一、示例
- 示例 1:
- 示例 2:
- 二、应用场景
- 三、解题思路
- 方法一:递归判断
- 方法二:迭代判断(借助队列)
- 四、Go语言实现
- 1. 数据结构定义
- 2. 方法一:递归法
- 3. 方法二:迭代法(使用队列)
- 五、测试样例
- 六、复杂度分析
- 七、可视化理解
- 八、变种与扩展
- 九、总结
给定一棵二叉树,判断这棵树是否是对称的。对称的含义是:这棵树的左子树和右子树在结构上是镜像对称的,且对应节点的值相等。
一、示例
示例 1:
1 /\ 22 /\/\ 3443 输出:true
示例 2:
1 /\ 22 \\ 33 http://www.devze.com输出:false
二、应用场LpwMKYKIO景
- • 用户界面或布局中验证左右对称性
- • 算法竞赛题目或笔试面试常考
- • 树结构可视化或分析工具中,对称性判断用于简化处理
三、解题思路
本问题的关键在于:比较树的左子树和右子树是否镜像对称。
我们可以采用两种方法:
方法一:递归判断
判断左右子树是否满足以下三个条件:
- 左子树的左子树和右子树的右子树对称;
- 左子树的右子树和右子树的左子树对称;
- 当前两个节点值相同。
方法二:迭代判断(借助队列)
使用队列存储成对的节点,每次成对弹出并比较:
- • 若都为空,继续;
- • 若一个为空另一个不为空 → 不对称;
- • 值不相等编程 → 不对称;
- • 否则将子节点成对压入队列,继续判断。
四、Go语言实现
1. 数据结构定义
packagemain import"fmt" typeTreeNodestruct{ Valint Left*TreeNode Right*TreeNode }
2. 方法一:递归法
funcisSymmetric(root*TreeNode)bool{ ifroot==nil{ returntrue } returnisMirror(root.Left,root.Right) } funcisMirror(left,right*TreandroideNode)bool{ ifleft==nil&&right==nil{ returntrue } ifleft==nil||right==nil{ returnfalse } ifleft.Val!=right.Val{ returnfalse } returnisMirror(left.Left,right.Right)&&isMirror(left.Right,right.Left) }
3. 方法二:迭代法(使用队列)
funcisSymmetricIterative(root*TreeNode)bool{ ifroot==nil{ returntrue } queue:=[]*TreeNode{root.Left,root.Right} forlen(queue)>0{ left:=queue[0] right:=queue[1] queue=queue[2:] ifleft==nil&&right==nil{ continue } ifleft==nil||right==nil||left.Val!=right.Val{ returnfalse } queue=append(queue,left.Left,right.Right) queue=append(queue,left.Right,right.Left) } returntrue }
五、测试样例
funcmain(){ //构建对称二叉树 root:=&TreeNode{Val:1} root.Left=&TreeNode{Val:2} root.Right=&TreeNode{Val:2} root.Left.Left=&TreeNode{Val:3} root.Left.Right=&TreeNode{Val:4} root.Right.Left=&TreeNode{Val:4} root.Right.Right=&TreeNode{Val:3} fmt.Println("递归判断结果:",isSymmetric(root))//true fmt.Println("迭代判断结果:",isSymmetricIterative(root))//true }
六、复杂度分析
方式 | 时间复杂度 | 空间复杂度 |
---|---|---|
递归法 | O(n) | O(h) |
迭代法 | O(n) | O(n) |
- n 表示节点数量;
- h 表示树的高度(递归调用栈的深度);
- 迭代方法使用了队列,需编程要额外 O(n) 空间存储节点。
七、可视化理解
将二叉树从中心线对折,看左、右两部分是否完全重合,节点值是否相等。
镜像对称结构满足:
left.Left
==right.Right
left.Right
==right.Left
八、变种与扩展
- 1. 判断 N 叉树是否镜像对称:需要成对比较左右子节点;
- 2. 输出是否对称的最小修改操作:可结合动态规划思想;
- 3. 判断对称层级:例如仅判断前两层是否对称。
九、总结
内容 | 说明 |
---|---|
核心判断条件 | 左右子树是否镜像结构,对应节点值是否相等 |
递归 vs 迭代 | 递归写法更直观,迭代适合大树或避免栈溢出 |
技巧点 | 左-右子树配对判断,使用队列模拟递归过程 |
实用价值 | 面试高频,掌握树结构对称性判断通用技巧 |
以上就是使用Go语言判断二叉树是否对称的方法小结的详细内容,更多关于Go判断二叉树对称的资料请关注编程客栈(www.devze.com)其它相关文章!
精彩评论