该题目来源于牛客网《剑指offer》专题。

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

Go语言实现:

方法一:递归

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
return symmetric(root, root)
}

func symmetric(t1 *TreeNode, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
return (t1.Val == t2.Val) && symmetric(t1.Left, t2.Right) &&
symmetric(t1.Right, t2.Left)
}

方法二:迭代

利用队列来进行迭代,队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像。

func isSymmetric(root *TreeNode) bool {
l := list.New()
l.PushBack(root)
l.PushBack(root)
for l.Len() > 0 { //list初始化后不放元素也不为空,所以不能用nil判断
t1 := l.Front().Value.(*TreeNode)
l.Remove(l.Front())
t2 := l.Front().Value.(*TreeNode)
l.Remove(l.Front()) if t1 == nil && t2 == nil {
continue //此处不能直接返回true,左右完了,还有右左
}
if t1 == nil || t2 == nil {
return false
}
if t1.Val != t2.Val {
return false
} l.PushBack(t1.Left)
l.PushBack(t2.Right)
l.PushBack(t1.Right)
l.PushBack(t2.Left)
} return true
}
05-11 18:21
查看更多