# 0101. 對稱二叉樹 ## 題目地址(101. 對稱二叉樹) <https://leetcode-cn.com/problems/symmetric-tree/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹，檢查它是否是鏡像對稱的。 例如，二叉樹 [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 進階： 你可以運用遞歸和迭代兩種方法解決這個問題嗎？ ``` ``` ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - bloomberg - linkedin - microsoft ## 前置知識 - [二叉樹](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 思路 看到這題的時候，我的第一直覺是 DFS。然后我就想:`如果左子樹是鏡像，并且右子樹也是鏡像，是不是就說明整體是鏡像？`。經過幾秒的思考， 這顯然是不對的，不符合題意。  很明顯其中左子樹中的節點會和右子樹中的節點進行比較，我把比較的元素進行了顏色區分，方便大家看。 這里我的想法是：`遍歷每一個節點的時候，我都可以通過某種方法知道它對應的對稱節點是誰。這樣的話我直接比較兩者是否一致就行了。` 最初我的想法是兩次遍歷，第一次遍歷的同時將遍歷結果存儲到哈希表中，然后第二次遍歷去哈希表取。 這種方法可行，但是需要 N 的空間（N 為節點總數）。我想到如果兩者可以同時進行遍歷，是不是就省去了哈希表的開銷。  如果不明白的話，我舉個簡單例子： ``` <pre class="calibre18">``` 給定一個數組，檢查它是否是鏡像對稱的。例如，數組 [1,2,2,3,2,2,1] 是對稱的。 ``` ``` 如果用哈希表的話大概是： ``` <pre class="calibre18">``` seen = dict() <span class="hljs-keyword">for</span> i, num <span class="hljs-keyword">in</span> enumerate(nums): seen[i] = num <span class="hljs-keyword">for</span> i, num <span class="hljs-keyword">in</span> enumerate(nums): <span class="hljs-keyword">if</span> seen[len(nums) - <span class="hljs-params">1</span> - i] != num: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> ``` ``` 而同時遍歷的話大概是這樣的： ``` <pre class="calibre18">``` l = <span class="hljs-params">0</span> r = len(nums) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> l < r: <span class="hljs-keyword">if</span> nums[l] != nums[r]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> l += <span class="hljs-params">1</span> r -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> ``` ``` > 其實更像本題一點的話應該是從中間分別向兩邊擴展 ?? ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isSymmetric</span><span class="hljs-params">(self, root: TreeNode)</span> -> bool:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(root1, root2)</span>:</span> <span class="hljs-keyword">if</span> root1 == root2: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root1 <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> root2: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">if</span> root1.val != root2.val: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> dfs(root1.left, root2.right) <span class="hljs-keyword">and</span> dfs(root1.right, root2.left) <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">return</span> dfs(root.left, root.right) ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N)，其中 N 為節點數。 - 空間復雜度：遞歸的深度最高為節點數，因此空間復雜度是 O(N)O(N)O(N)，其中 N 為節點數。 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。