LeetCode 對稱二叉樹：遞歸與迭代雙解法

題目描述

判斷一棵二叉樹是否鏡像對稱。即左子樹與右子樹結構互為鏡像，對應節點值相等。

遞歸解法

輔助函數比較兩棵樹是否互為鏡像：若兩根節點均為空返回真；若一空一非空返回假；值不等返回假；否則遞歸比較左樹的左與右樹的右、左樹的右與右樹的左。

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        return self._isMirror(root.left, root.right)

    def _isMirror(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return self._isMirror(left.left, right.right) and \
               self._isMirror(left.right, right.left)

迭代解法

使用兩個棧（或隊列）同步遍歷：將左子樹根、右子樹根分別壓入。每次彈出兩節點比較，若值不等返回假；然後將左節點的左、右子節點按順序壓入第一棧，右節點的右、左子節點壓入第二棧。最後檢查兩棧是否同時為空。

    def isSymmetric_iterate(self, root):
        if not root:
            return True
        stack1, stack2 = [root.left], [root.right]
        while stack1 and stack2:
            node1, node2 = stack1.pop(), stack2.pop()
            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            stack1.append(node1.left)
            stack1.append(node1.right)
            stack2.append(node2.right)
            stack2.append(node2.left)
        return not stack1 and not stack2

複雜度

• 時間：O(n)，每個節點訪問一次。
• 空間：O(n)，最壞情況棧存儲所有節點。