給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹?[1,2,2,3,4,4,3]?是對稱的。

    1/ \2   2/ \ / \
3  4 4  3

但是下面這個?[1,2,2,null,3,null,3]?則不是鏡像對稱的:

    1/ \2   2\   \3    3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

方法一：遞歸

如果一個樹的左子樹與右子樹鏡像對稱，那么這個樹是對稱的。

因此，該問題可以轉化為：兩個樹在什么情況下互為鏡像？

如果同時滿足下面的條件，兩個樹互為鏡像：

1. 它們的兩個根結點具有相同的值。
2. 每個樹的右子樹都與另一個樹的左子樹鏡像對稱。

就像人站在鏡子前審視自己那樣。鏡中的反射與現實中的人具有相同的頭部，但反射的右臂對應于人的左臂，反之亦然。

上面的解釋可以很自然地轉換為一個遞歸函數，如下所示：

public boolean isSymmetric(TreeNode root) {return isMirror(root, root);
}public 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.right, t2.left)&& isMirror(t1.left, t2.right);
}

復雜度分析

• 時間復雜度：O(n)O(n)。因為我們遍歷整個輸入樹一次，所以總的運行時間為?O(n)O(n)，其中?nn?是樹中結點的總數。
• 空間復雜度：遞歸調用的次數受樹的高度限制。在最糟糕的情況下，樹是線性的，其高度為?O(n)O(n)。因此，在最糟糕的情況下，由棧上的遞歸調用造成的空間復雜度為?O(n)O(n)。

方法二：迭代

除了遞歸的方法外，我們也可以利用隊列進行迭代。隊列中每兩個連續的結點應該是相等的，而且它們的子樹互為鏡像。最初，隊列中包含的是?root?以及?root。該算法的工作原理類似于 BFS，但存在一些關鍵差異。每次提取兩個結點并比較它們的值。然后，將兩個結點的左右子結點按相反的順序插入隊列中。當隊列為空時，或者我們檢測到樹不對稱（即從隊列中取出兩個不相等的連續結點）時，該算法結束。

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

復雜度分析

• 時間復雜度：O(n)O(n)。因為我們遍歷整個輸入樹一次，所以總的運行時間為?O(n)O(n)，其中?nn?是樹中結點的總數。
• 空間復雜度：搜索隊列需要額外的空間。在最糟糕的情況下，我們不得不向隊列中插入?O(n)O(n)?個結點。因此，空間復雜度為?O(n)O(n)。