基礎圖論題目 Symmetric Tree Leetcode #101

這題題目在這裡:

題目會給定一顆樹，要求我們判定這棵樹是不是左右鏡像對稱(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:

• The number of nodes in the tree is in the range [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