這題題目在這裡:
題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
測試範例:
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
約束條件:
Constraints:
[1, 1000]
.-100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
演算法:
使用到的技巧和前一題Same Tree類似。
這題一樣可以用DFS或是BFS來解,剛好呼應Follow-up 的Recursive遞迴解和 Iterative 迭代解。
範例一的暗示已經很清楚,就是假想樹的正中間有一條虛擬的分割線,把樹拆成左右兩顆子樹,判斷左子樹、右子樹是否以分割線為對稱軸,左右鏡像對稱。
DFS、BFS的核心觀念一樣依循同樣的原則:
若左、右子樹皆非空,則判斷當下節點值是否相同,並且用同樣的邏輯去判斷下一層的子樹,在DFS裡面就是遞迴呼叫,在BFS裡面就是推入對應成雙成對鏡像的節點。
DFS程式碼:
class Solution:
def check_symm(self, p:TreeNode, q:TreeNode)->bool:
# Stop condition
if not(p and q):
return p == q
# General case:
# both p and q exist, check symmetry on both child nodes
return p.val == q.val and self.check_symm( p.left, q.right) and self.check_symm( p.right, q.left)
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
# empty tree
return True
else:
# check symmetry by function check_symm
return self.check_symm( root.left, root.right)
時間複雜度:
O( n ) 每個節點至多拜訪一次。
空間複雜度:
O( n ) 樹高最深為O(n),當這顆樹為向左歪斜,或者向右歪斜的時候。
BFS程式碼:
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
traversal_queue = deque( [root, root] )
while traversal_queue:
# Left half
L = traversal_queue.popleft()
# Right half
R = traversal_queue.popleft()
# Both Left and Right are empty, i.e., NULL node
if (not L) and (not R): continue
# Either L or R is empty, or
# L's value is not equal to R's value
if (not L) or (not R) or ( L.val != R.val):
return False
# Keep compare Left subtree and Right subtree with symmetry judgement
traversal_queue.append(L.right)
traversal_queue.append(R.left)
traversal_queue.append(R.right)
traversal_queue.append(L.left)
return True
時間複雜度:
O( n ) 每個節點至多拜訪一次。
空間複雜度:
O( n ) 佇列最長為O(n),每個節點最多推入佇列一次,從佇列取出一次。
Reference:
[1] Python O( n ) by DFS and BFS. 87%+ [w/ Visualization] — Symmetric Tree — LeetCode