題目說明

101. Symmetric Tree
     給定一個二元樹，判斷它是否為「鏡像對稱」的。

範例：
Input:

1

/
2 2
/ \ /
3 4 4 3

Output:

true

Input:

1

/
2 2
\
3 3

Output:

false

程式碼

Python 解法
解法 1：遞迴

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root: TreeNode) -> bool:
if not root:
return True
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)

解法 2：BFS（Queue）

from collections import deque
def isSymmetric(root: TreeNode) -> bool:
if not root:
return True
queue = deque([(root.left, root.right)])
while queue:
t1, t2 = queue.popleft()
if not t1 and not t2:
continue
if not t1 or not t2 or t1.val != t2.val:
return False
queue.append((t1.left, t2.right))
queue.append((t1.right, t2.left))
return True

Java 解法

解法 1：遞迴

public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val) &&
isMirror(t1.left, t2.right) &&
isMirror(t1.right, t2.left);
}
}

解法 2：BFS（Queue）

import java.util.*;
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue queue = new LinkedList<>();
queue.add(root.left);
queue.add(root.right);
while (!queue.isEmpty()) {
TreeNode t1 = queue.poll();
TreeNode t2 = queue.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null || t1.val != t2.val) return false;
queue.add(t1.left);
queue.add(t2.right);
queue.add(t1.right);
queue.add(t2.left);
}
return true;
}
}

複雜度分析

• 時間複雜度：O(n)，每個節點至少會被比較一次。
• 空間複雜度：
  • 遞迴：O(h)，h 為樹的高度（最壞 O(n)，最佳 O(log n)）。
  • BFS：O(w)，w 為樹的最大寬度。