2025/09/06 leetCode101. 對稱二叉樹
一、遞歸解法：
解法1
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: def isMirror(t1, t2): if not t1 and not t2: return True if not t1 or not t2: return False return t1.val == t2.val and \ isMirror(t1.left, t2.right) and \ isMirror(t1.right, t2.left) return isMirror(root.left, root.right)
以下兩句的順序不能顛倒：
if not t1 and not t2: return True if not t1 or not t2: return False
知識點：python中的or
在 Python 中：
①
A or B 表示：如果 A 為真（truthy），就返回 A；否則返回 B。
它是 邏輯“或”：只要有一個為真，結果就為真。
②Python 中的 or 是返回值表達式，不是單純布爾值。
a = 0 b = 123 print(a or b) # ?? 123，因為 a 為 False，返回 b
| 表達式 | 結果 | 解釋 |
| 0 or 123 | 123 | 0 為假 → 返回 123 |
| [] or [1] | [1] | 空列表為假 → 返回非空列表 |
| 'a' or 'b' | 'a' | 'a' 為真 → 返回 'a' |
| None or 1 | 1 | None 為假 → 返回 1 |
③用途
name = user_input or "Default Name"
如果用戶輸入是空的，就使用默認值 "Default Name"
④and的優(yōu)先級高于or
⑤區(qū)別：
C/C++ 的 || 只是返回布爾值（true / false）
Python 的 or 會返回第一個為真的值或最后一個為假值，既是邏輯運算符也是表達式運算符（邏輯判斷里是“有真則真”，表達式里是“遇真返回真值”）
解法2：
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True return self.compare(root.left, root.right) def compare(self, left, right): # 1.排除空節(jié)點的情況 if left == None and right == None: return True elif left != None and right == None: return False elif left == None and right != None: return False # 2.排除數值不相同的情況 elif left.val != right.val: return False # 3. 剩余左右節(jié)點均不為空，且數值相同的情況 # 此時做遞歸，對下一層做判斷 outside = self.compare(left.left, right.right) inside = self.compare(left.right, right.left) return inside and outside
二、迭代法
解法1：使用隊列
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True queue = collections.deque() queue.append(root.left) queue.append(root.right) while queue: leftNode = queue.popleft() rightNode = queue.popleft() if not leftNode and not rightNode: continue if not leftNode or not rightNode or leftNode.val != rightNode.val: return False queue.append(leftNode.left) queue.append(rightNode.right) queue.append(leftNode.right) queue.append(rightNode.left) return True
解法2：使用棧
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True st = [] st.append(root.left) st.append(root.right) while st: rightNode = st.pop() leftNode = st.pop() if not leftNode and not rightNode: continue if not leftNode or not rightNode or leftNode.val != rightNode.val: return False st.append(leftNode.left) st.append(rightNode.right) st.append(leftNode.right) st.append(rightNode.left) return True
三、層次遍歷：
自己開始做這題也想到用層序遍歷，但是很多細節(jié)問題沒有想到，包括怎么把每一次的數值進行比較的問題，沒有想到直接把每一層的數值列表倒序進行比較就可以。
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True queue = collections.deque() queue.append(root.left) queue.append(root.right) while queue: level_size = len(queue) if level_size % 2 != 0: return False level_vals = [] for _ in range(level_size): node = queue.popleft() if node: level_vals.append(node.val) queue.append(node.left) queue.append(node.right) else: level_vals.append(None) if level_vals != level_vals[::-1]: return False return True
遞歸法：
class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: return self.compare(p, q) def compare(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True elif not p or not q: return False else: return p.val == q.val and self.compare(p.left, q.left) and self.compare(p.right, q.right)
層序遍歷：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if not p or not q: return False queue_p = collections.deque([p]) queue_q = collections.deque([q]) while queue_p and queue_q: level_size_p = len(queue_p) level_size_q = len(queue_q) if level_size_p != level_size_q: return False level_vals_p = [] level_vals_q = [] for _ in range(level_size_p): node_p = queue_p.popleft() node_q = queue_q.popleft() if node_p and node_q: level_vals_p.append(node_p.val) level_vals_q.append(node_q.val) queue_p.append(node_p.left) queue_p.append(node_p.right) queue_q.append(node_q.left) queue_q.append(node_q.right) elif not node_p and not node_q: level_vals_p.append(None) level_vals_q.append(None) else: return False if level_vals_p != level_vals_q: return False return True
主函數用棧輔助前序遍歷root，用遞歸函數compare將root的子樹與subRoot對比。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: st = [root] while st: node = st.pop() if self.compare(node, subRoot): return True else: if node.right: st.append(node.right) if node.left: st.append(node.left) return False def compare(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True elif not p or not q: return False else: return p.val == q.val and \ self.compare(p.left, q.left) and \ self.compare(p.right, q.right)
浙公網安備 33010602011771號