开发者

使用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. 1. 判断 N 叉树是否镜像对称:需要成对比较左右子节点;
              2. 2. 输出是否对称的最小修改操作:可结合动态规划思想;
              3. 3. 判断对称层级:例如仅判断前两层是否对称。

              九、总结

              内容说明
              核心判断条件左右子树是否镜像结构,对应节点值是否相等
              递归 vs 迭代递归写法更直观,迭代适合大树或避免栈溢出
              技巧点左-右子树配对判断,使用队列模拟递归过程
              实用价值面试高频,掌握树结构对称性判断通用技巧

              以上就是使用Go语言判断二叉树是否对称的方法小结的详细内容,更多关于Go判断二叉树对称的资料请关注编程客栈(www.devze.com)其它相关文章!

              0

              上一篇:

              下一篇:

              精彩评论

              暂无评论...
              验证码 换一张
              取 消

              最新开发

              开发排行榜