101. Symmetric Tree

题目 #

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

思路1 #

分析 #

  • 就是递归看节点左右子树是否对称嘛

代码实现 # 

 1func checkSymmetric(a *TreeNode, b *TreeNode) bool {
 2	if a == nil && b == nil {
 3		return true
 4	}
 5	if a == nil || b == nil {
 6		return false
 7	}
 8
 9	return a.Val == b.Val && checkSymmetric(a.Left, b.Right) && checkSymmetric(a.Right, b.Left)
10}
11
12func isSymmetric(root *TreeNode) bool {
13	return checkSymmetric(root.Left, root.Right)
14}

思路2 #

分析 #

  • 不用递归，搞两个链表，广度优先遍历，只不过顺序反一下

代码实现 # 

 1func isSymmetric(root *TreeNode) bool {
 2	if root.Left == nil && root.Right == nil {
 3		return true
 4	}
 5	if root.Left == nil || root.Right == nil {
 6		return false
 7	}
 8	var l list.List
 9	var r list.List
10	l.PushBack(root.Left)
11	r.PushBack(root.Right)
12	for l.Len() != 0 {
13		lt := l.Front().Value.(*TreeNode)
14		l.Remove(l.Front())
15		rt := r.Front().Value.(*TreeNode)
16		r.Remove(r.Front())
17		if lt == nil && rt == nil {
18			continue
19		}
20		if (lt == nil || rt == nil) || lt.Val != rt.Val {
21			return false
22		}
23
24		l.PushBack(lt.Left)
25		r.PushBack(rt.Right)
26		l.PushBack(lt.Right)
27		r.PushBack(rt.Left)
28	}
29	return true
30}