python對稱二叉樹該如何理解

# Python對稱二叉樹該如何理解

## 一、什么是對稱二叉樹

對稱二叉樹（Symmetric Binary Tree）是指一棵二叉樹的左右子樹在結構上呈現鏡像對稱的特性。具體表現為：

1. 根節點的左右子樹互為鏡像
2. 左子樹的左子樹與右子樹的右子樹對稱
3. 左子樹的右子樹與右子樹的左子樹對稱

示例對稱二叉樹：

 1

/
2 2 / \ /
3 4 4 3

## 二、Python實現對稱二叉樹的判斷

### 方法一：遞歸解法

```python
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
    return compare(root.left, root.right)

def compare(left: TreeNode, right: TreeNode) -> bool:
    if not left and not right:
        return True
    if not left or not right or left.val != right.val:
        return False
    return compare(left.left, right.right) and compare(left.right, right.left)

遞歸過程解析： 1. 基線條件：當兩個節點都為空時返回True 2. 不對稱條件：任一節點為空或節點值不等 3. 遞歸比較：左左vs右右，左右vs右左

方法二：迭代解法（使用隊列）

from collections import deque

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

迭代過程特點： - 使用隊列代替系統調用棧 - 每次比較一對節點，并成對入隊子節點 - 空間復雜度O(n)，適合深度較大的樹

三、算法復雜度分析

注：n為節點總數，h為樹的高度

四、實際應用場景

1. 數據結構驗證：驗證樹結構的對稱性
2. 鏡像系統設計：如游戲場景的對稱地圖生成
3. 生物信息學：DNA序列的對稱性分析
4. 編譯器設計：語法樹的對稱性檢查

五、常見誤區與調試技巧

常見錯誤： 1. 忽略空節點情況導致NoneType錯誤 2. 錯誤比較左左vs左右（應為左左vs右右） 3. 遞歸終止條件不完整

調試建議：

# 打印樹結構輔助調試
def print_tree(node, level=0):
    if node:
        print_tree(node.right, level + 1)
        print(' ' * 4 * level + '->', node.val)
        print_tree(node.left, level + 1)

六、LeetCode實戰練習

推薦題目： - 101. 對稱二叉樹 - 100. 相同的樹（變式練習） - 226. 翻轉二叉樹（關聯概念）

七、擴展思考

1. N叉樹的對稱性判斷：需要比較所有子節點的對稱性
2. 帶權對稱樹：考慮節點權重而不僅是結構
3. 部分對稱樹：統計最大對稱子樹的問題

理解對稱二叉樹的關鍵在于培養遞歸思維和鏡像比較的能力，這是許多更復雜樹結構算法的基礎。 “`