寫在前面

本專欄專注于分析與講解【面試經典150】算法，兩到三天更新一篇文章，歡迎催更……

專欄內容以分析題目為主，并附帶一些對于本題涉及到的數據結構等內容進行回顧與總結，文章結構大致如下，部分內容會有增刪：

• Tag：介紹本題牽涉到的知識點、數據結構；
• 題目來源：貼上題目的鏈接，方便大家查找題目并完成練習；
• 題目解讀：復述題目（確保自己真的理解題目意思），并強調一些題目重點信息；
• 解題思路：介紹一些解題思路，每種解題思路包括思路講解、實現代碼以及復雜度分析；
• 知識回憶：針對今天介紹的題目中的重點內容、數據結構進行回顧總結。

---

Tag

【遞歸】【迭代】【二叉樹】

---

題目來源

101. 對稱二叉樹

---

解題思路

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

因此，問題轉換為：兩棵樹在什么情況下是互為鏡像的，找出使兩棵樹互為鏡像的條件，根據條件即可結局對稱問題。

鏡像條件如下：

• 兩棵樹的兩個根節點具有相同的值；
• 每棵樹的右子樹都要與另一棵樹的左子樹鏡像對稱。

同時滿足以上兩個條件即可判斷出兩棵樹是對稱的。

二叉樹問題通常都有兩種遞歸和迭代的解法。

方法一：遞歸

遞歸出口是什么？

遞歸出口即可以直接判斷的情況，包括：

• 兩個節點都為空時，直接返回 true；
• 一個節點為空，另一個不為空，返回 false。

如何往下遞？

當前的兩個節點表示的子樹是否是對稱的，取決于當前兩節點的值以及左右子樹是否對稱。

只有當前兩節點的值相等并且左右子樹對稱，這兩個節點表示的子樹才是對稱的。

算法

實現一個判斷兩個節點 p 和 q 表示的子樹是否是對稱的函數 check：

• 如果 p = nullptr 并且 q = nullptr，直接返回 true；
• 如果 p ≠ nullptr 或者 q ≠ nullptr，直接返回 false；
• 最后 p 和 q 表示的子樹是否是對稱與 p->val == q->val && check(p->left, q->right) && check(p->right, q->left) 一致，直接返回該表達式。

調用 check(root, root) 即得到最終答案。

復雜度分析

時間復雜度：$O(n)$，$n$ 為二叉樹中節點的數量。

空間復雜度：$O(n)$。

方法二：迭代

思路與算法

使用迭代解法需要用到隊列。

首先我們引入一個隊列，初始化時我們把根節點入隊兩次。每次提取兩個節點并比較它們的值（隊列中每兩個連續的節點應該是相等的，而且它們的子樹互為鏡像），然后將兩個節點的左右子節點按相反的順序插入隊列中。

當隊列為空時，或者我們檢測到樹不對稱，即從隊列中取出兩個不相等的連續節點時，該算法結束。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool check(TreeNode* u, TreeNode *v) {queue<TreeNode*> q;q.push(u); q.push(v);while (!q.empty()) {u = q.front(); q.pop();v = q.front(); q.pop();if (!u && !v)continue;if (!u || !v ||(u->val != v->val))return false;q.push(u->left);q.push(v->right);q.push(u->right);q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

復雜度分析

時間復雜度：$O(n)$，$n$ 為二叉樹中節點的數量。

空間復雜度：$O(n)$，因為二叉樹中的節點最多入隊、出隊一次，因此漸進的時間復雜度為 $O(n)$。

---

寫在最后

如果文章內容有任何錯誤或者您對文章有任何疑問，歡迎私信博主或者在評論區指出 💬💬💬。

如果大家有更優的時間、空間復雜度方法，歡迎評論區交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點一個 👍 哦。