寫在前面

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

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

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

---

Tag

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

---

題目來源

226. 翻轉二叉樹

---

題目解讀

如示例 1 所示，翻轉就是將二叉樹的每個節點的所有子樹都左右交換，原來父節點左子樹現在變成了父節點的右子樹，原來是父節點右子樹現在變成了父節點的左子樹。

---

解題思路

二叉樹問題有兩種解題方法，遞歸與迭代。

方法一：遞歸

思想

從根節點開始，先翻轉左子樹并記錄翻轉后的根節點 leftRoot，再翻轉右子樹并記錄翻轉后的根節點 rightRoot，然后將根節點的左子樹替換為 rightRoot，右子樹替換為 leftRoot。

算法

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr){return nullptr;}TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;}
};

復雜度分析

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

空間復雜度：$O(n)$，最壞情況下二叉樹退化成一條鏈，占用的棧空間為 $O(n)$。

方法二：迭代

思路

從根節點往下，按層枚舉所有的節點，將每一個節點的左右子樹進行交換就可以了。

算法

根節點為空，直接返回 nullptr。

根節點非空，則維護一個隊列 q 用來記錄節點。按照層序遍歷的模板，依次交換左右子樹：

• 首先，將根節點加入到隊列 q；
• 接著，主要 q 不為空，就執行以下操作：
  • 彈出隊首節點 node；
  • 只要該節點有子樹（左右子樹有一個節點或左右子樹都存在），則交換兩個子節點；
  • 將非空子節點加入到隊列中。
• 最后返回翻轉后的根節點 root。

/*** 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:TreeNode* invertTree(TreeNode* root) {if (root == nullptr) {return nullptr;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();if (node->left != nullptr || node->right != nullptr) {swap(node->left, node->right);}if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}return root;}
};

復雜度分析

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

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

---

寫在最后

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

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

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