1、題目描述

給定一個二叉樹，檢查它是否是鏡像對稱的。

2、代碼詳解

2.1 遞歸寫法

# Definition for a binary tree node.

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object):

# 遞歸寫法

def isSymmetric(self, root):

"""

:type root: TreeNode

:rtype: bool

"""

return self.isMirror(root, root)

def isMirror(self, root1, root2):

# 遞歸結束條件

if not root1 and not root2: # 條件1：都為空指針則返回 true

return True

elif not root1 or not root2: # 條件2：只有一個為空則返回 false

return False

return (root1.val == root2.val) and \

self.isMirror(root1.left, root2.right) and \

self.isMirror(root1.right, root2.left)

pNode1 = TreeNode(1)

pNode2 = TreeNode(2)

pNode3 = TreeNode(2)

pNode4 = TreeNode(3)

pNode5 = TreeNode(4)

pNode6 = TreeNode(4)

pNode7 = TreeNode(3)

pNode1.left = pNode2

pNode1.right = pNode3

pNode2.left = pNode4

pNode2.right = pNode5

pNode3.left = pNode6

pNode3.right = pNode7

S = Solution()

print(S.isSymmetric(pNode1)) # True

時間復雜度是 O(n)，因為要遍歷 n 個節點

空間復雜度是 O(n)，是遞歸的深度，也就是跟樹高度有關，最壞情況下樹變成一個鏈表結構，高度是n。

2.2 迭代寫法

用隊列來實現

首先從隊列中拿出兩個節點(left 和 right)比較

將 left 的 left 節點和 right 的 right 節點放入隊列

將 left 的 right 節點和 right 的 left 節點放入隊列

時間復雜度是 O(n)，空間復雜度是 O(n)

class Solution(object):

def isSymmetric(self, root):

"""

:type root: TreeNode

:rtype: bool

"""

if not root or not (root.left or root.right):

return True

# 用隊列保存節點

queue = [root.left,root.right]

while queue:

# 從隊列中取出兩個節點，再比較這兩個節點

left = queue.pop(0)

right = queue.pop(0)

# 如果兩個節點都為空就繼續循環，兩者有一個為空就返回false

if not (left or right):

continue

if not (left and right):

return False

if left.val!=right.val:

return False

# 將左節點的左孩子， 右節點的右孩子放入隊列

queue.append(left.left)

queue.append(right.right)

# 將左節點的右孩子，右節點的左孩子放入隊列

queue.append(left.right)

queue.append(right.left)

return True

本文地址：https://blog.csdn.net/IOT_victor/article/details/107117445

希望與廣大網友互動？？

點此進行留言吧！

總結

以上是生活随笔為你收集整理的python数据结构递归树_python数据结构（对称二叉树递归和迭代）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。