该题目来源于牛客网《剑指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
}