題目 ：給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1
/ \
2 2
\ \
3 3
用遞歸和隊列實現(xiàn)
#遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
:
def
isSymmetric
(
self
,
root
:
TreeNode
)
-
>
bool
:
if
not
root
:
# 先判斷根節(jié)點是否為空
return
True
return
self
.
isMirror
(
root
.
left
,
root
.
right
)
# 分成左子樹和右子樹判斷
def
isMirror
(
self
,
p
,
q
)
:
# 判斷兩棵樹是否是鏡像樹
if
not
p
and
not
q
:
# 根節(jié)點都為空，是
return
True
if
not
p
or
not
q
:
# 其中有一棵為空，不是
return
False
l
=
self
.
isMirror
(
p
.
left
,
q
.
right
)
# p的左子樹和q的右子樹是否相同
r
=
self
.
isMirror
(
p
.
right
,
q
.
left
)
# p的右子樹和q的左子樹是否相同
return
p
.
val
==
q
.
val
and
l
and
r
# 值相等，并且p的左=q的右，p的右=q的左
# 方法二 隊列實現(xiàn)
class
Solution
:
def
isSymmetric
(
self
,
root
)
:
"""
隊列
:param root:
:return:
"""
if
not
root
:
return
True
node_queue
=
[
root
.
left
,
root
.
right
]
# 在空隊列中加入左子樹和右子樹
while
node_queue
:
left
=
node_queue
.
pop
(
0
)
# 依次彈出兩個元素
right
=
node_queue
.
pop
(
0
)
if
not
right
and
not
left
:
# 如果均為空，繼續(xù)下一個循環(huán)
continue
if
not
right
or
not
left
:
# 如果只有一個為空，返回False
return
False
if
left
.
val
!=
right
.
val
:
# 都非空，再判斷值是否相等
return
False
node_queue
.
append
(
left
.
left
)
# 將兩個左右子樹的左右子樹逆序加入隊列
node_queue
.
append
(
right
.
right
)
node_queue
.
append
(
left
.
right
)
node_queue
.
append
(
right
.
left
)
#node_queue.extend([left.left, right.right, left.right, right.left]) 或者用這一句話寫
return
True
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
