使用Go语言判断二叉树是否对称的方法小结

目录

• 一、示例
• 示例 1：
• 示例 2：
• 二、应用场景
• 三、解题思路
• 方法一：递归判断
• 方法二：迭代判断（借助队列）
• 四、Go语言实现
• 1. 数据结构定义
• 2. 方法一：递归法
• 3. 方法二：迭代法（使用队列）
• 五、测试样例
• 六、复杂度分析
• 七、可视化理解
• 八、变种与扩展
• 九、总结

给定一棵二叉树，判断这棵树是否是对称的。对称的含义是：这棵树的左子树和右子树在结构上是镜像对称的，且对应节点的值相等。

    1
   / 
  2   2
 /  / 
3  4 4  3

输出：true

    1
   / 
  2   2
      
   3    3

输出：false

• • 用户界面或布局中验证左右对称性
• • 算法竞赛题目或笔试面试常考
• • 树结构可视化或分析工具中，对称性判断用于简化处理

本问题的关键在于：比较树的左子树和右子树是否镜像对称。

我们可以采用两种方法：

判断左右子树是否满足以下三个条件：

• 左子树的左子树和右子树的右子树对称；
• 左子树的右子树和右子树的左子树对称；
• 当前两个节点值相同。

使用队列存储成对的节点，每次成对弹出并比较：

• • 若都为空，继续；
• • 若一个为空另一个不为空 → 不对称；
• • 值不相等 → 不对称；
• • 否则将子节点成对压入队列，继续判断。

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}

func isMirror(left, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    if left.Val != right.Val {
        return false
    }
    return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}

func isSymmetricIterative(root *TreeNode) bool {
    if root == nil {
        return true
    }

    queue := []*TreeNode{root.Left, root.Right}

    for len(queue) > 0 {
        left := queue[0]
        right := queue[1]
        queue = queue[2:]

        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }

        queue = append(queue, left.Left, right.Right)
        queue = append(queue, left.Right, right.Left)
    }

    return true
}

func main() {
    // 构建对称二叉树
    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判断二叉树对称的资料请关注风君子博客其它相关文章！

您可能感兴趣的文章:

• go语言算法题解二叉树的拷贝、镜像和对称
• go语言算法题解二叉树的最小深度
• Go语言数据结构之二叉树可视化详解
• Go语言数据结构之二叉树必会知识点总结
• Go Java算法之二叉树的所有路径示例详解