这是树的第4篇算法,力扣链接。
给你一个二叉树的根节点
root
, 检查它是否轴对称。示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true
这道题最简单的思路是递归,左子叶要和右子叶比较来判断对称性。
func isSymmetric(root *TreeNode) bool {
return check(root, root)
}
func check(left, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
return left.Val == right.Val && check(left.Left, right.Right) && check(left.Right, right.Left)
}
也可以用广度优先遍历来判断是否为对称树:
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
queue1, queue2 := []*TreeNode{root.Left}, []*TreeNode{root.Right}
for len(queue1) > 0 && len(queue2) > 0 {
left := queue1[0]
queue1 = queue1[1:]
right := queue2[0]
queue2 = queue2[1:]
if left == nil && right == nil {
continue
}
if left == nil || right == nil || left.Val != right.Val {
return false
}
queue1 = append(queue1, left.Left)
queue2 = append(queue2, right.Right)
queue1 = append(queue1, left.Right)
queue2 = append(queue2, right.Left)
}
return len(queue1) == len(queue2) && len(queue1) == 0
}