系列目錄

88.合并兩個(gè)有序數(shù)組
52.螺旋數(shù)組
567.字符串的排列
643.子數(shù)組最大平均數(shù)
150.逆波蘭表達(dá)式
61.旋轉(zhuǎn)鏈表
160.相交鏈表
83.刪除排序鏈表中的重復(fù)元素
389.找不同
1491.去掉最低工資和最高工資后的工資平均值
896.單調(diào)序列
206.反轉(zhuǎn)鏈表
92.反轉(zhuǎn)鏈表II
141.環(huán)形鏈表
142.環(huán)型鏈表
21.合并兩個(gè)有序列表
24.兩輛交換鏈表中的節(jié)點(diǎn)
876.鏈表的中間節(jié)點(diǎn)
143. 重排鏈表
2.兩數(shù)相加
445.兩數(shù)相加II

---

---

前言

方法都是類似的～
遞歸是隱式調(diào)用棧(遞歸棧，無(wú)需手動(dòng)實(shí)現(xiàn))，迭代是顯式調(diào)用棧

---

144.二叉樹(shù)的前序遍歷

🌟遞歸

原題鏈接

C++
若未特殊標(biāo)明，以下題解均寫用C++

/*** 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:// 注意引用符void preorder(TreeNode* root, vector<int> &res) {if (root == nullptr)// preorder 函數(shù)被定義為返回 void 類型——不返回任何值// return; 僅僅是結(jié)束函數(shù)的執(zhí)行，并不返回任何值return;// 存入向量的末尾res.push_back(root->val);// 前序——根左右preorder(root->left, res);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode* root) {// 定義一個(gè) 矢量/向量——更準(zhǔn)確地說(shuō)是一個(gè)動(dòng)態(tài)數(shù)組vector<int> res;preorder(root, res);return res;}
};

94.二叉樹(shù)的中序遍歷

🌟遞歸+迭代

原題鏈接

C++
若未特殊標(biāo)明，以下題解均寫用C++

方法一 遞歸 (DFS )

/*** 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) {}* };*/// 二叉樹(shù)的中序遍歷
class Solution {
public:void inorder(TreeNode* root, vector<int>& res) {//可以另寫成if (!root)if (!root) return;// 中序——左根右——先插入最左邊的左孩子inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}
};

145.二叉樹(shù)的后序遍歷

🌟遞歸+迭代

原題鏈接

C++
若未特殊標(biāo)明，以下題解均寫用C++

方法一 遞歸 (DFS )

/*** 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) {}* };*/
// 二叉樹(shù)的后序遍歷
class Solution {
public:void postorder(TreeNode *root, vector<int> &res) {if (!root)return;// 后序——左右根postorder(root->left, res);postorder(root->right, res);// 左右都不存在才先插入根節(jié)點(diǎn)的值res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};

方法二 迭代

/*** 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:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;// 空樹(shù)if (!root) return res;// 定義一個(gè) 樹(shù)節(jié)點(diǎn)棧stack<TreeNode* > stk;TreeNode *prev = nullptr;// 樹(shù)沒(méi)遍歷完 或 棧非空while (root != nullptr || !stk.empty()) {// 樹(shù)沒(méi)遍歷完while (root != nullptr) {// 遍歷所有左節(jié)點(diǎn) 入棧// 將這個(gè)樹(shù)節(jié)點(diǎn) 入棧stk.emplace(root);root = root->left;}// 若此時(shí) root 為空// 更新 root root = stk.top();// 棧頂元素用完 彈出棧stk.pop();// 無(wú)右子節(jié)點(diǎn) 或 這個(gè)右子節(jié)點(diǎn)被遍歷過(guò)if (root->right == nullptr || root->right == prev) {res.emplace_back(root->val);// 標(biāo)記這個(gè)節(jié)點(diǎn)prev = root;root = nullptr;} // 有右子節(jié)點(diǎn)else { stk.emplace(root);root = root->right;}}return res;}
};

方法三 Morris遍歷

class Solution {
public:void addPath(vector<int> &vec, TreeNode *node) {int count = 0;while (node != nullptr) {++count;vec.emplace_back(node->val);node = node->right;}reverse(vec.end() - count, vec.end());}vector<int> postorderTraversal(TreeNode *root) {vector<int> res;if (root == nullptr) {return res;}TreeNode *p1 = root, *p2 = nullptr;while (p1 != nullptr) {p2 = p1->left;if (p2 != nullptr) {while (p2->right != nullptr && p2->right != p1) {p2 = p2->right;}if (p2->right == nullptr) {p2->right = p1;p1 = p1->left;continue;} else {p2->right = nullptr;addPath(res, p1->left);}}p1 = p1->right;}addPath(res, root);return res;}
};

Morris遍歷

Morris遍歷是一種高效的二叉樹(shù)遍歷算法，其顯著特點(diǎn)是能在不使用棧或隊(duì)列的情況下實(shí)現(xiàn)中序遍歷，且空間復(fù)雜度為O(1)

1. 基本思想
Morris遍歷的基本思想是利用葉子節(jié)點(diǎn)的空指針來(lái)存儲(chǔ)臨時(shí)信息，從而達(dá)到節(jié)省空間的目的
在遍歷過(guò)程中，Morris遍歷會(huì)修改樹(shù)中某些節(jié)點(diǎn)的指針指向，以便在遍歷時(shí)能夠方便地回溯到上一個(gè)節(jié)點(diǎn) 遍歷完成后，需要還原樹(shù)的結(jié)構(gòu)

2. 實(shí)現(xiàn)過(guò)程
Morris遍歷的實(shí)現(xiàn)過(guò)程可以分為以下幾個(gè)步驟：

• 對(duì)于當(dāng)前遍歷到的節(jié)點(diǎn)，如果它有左子節(jié)點(diǎn)，就找到左子樹(shù)中最右邊的節(jié)點(diǎn) (記為mostRight )，將其右子節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)
• 將當(dāng)前節(jié)點(diǎn)更新為其左子節(jié)點(diǎn)，繼續(xù)遍歷
• 如果當(dāng)前節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，就輸出當(dāng)前節(jié)點(diǎn)的值 (或進(jìn)行其他操作)，并將當(dāng)前節(jié)點(diǎn)更新為其右子節(jié)點(diǎn)
• 重復(fù)以上步驟，直到遍歷完整棵樹(shù)

3. 遍歷類型
Morris遍歷可以實(shí)現(xiàn)前序、中序和后序遍歷
具體實(shí)現(xiàn)時(shí)，需要根據(jù)遍歷的順序調(diào)整指針的指向和節(jié)點(diǎn)的訪問(wèn)順序

• 前序遍歷：在第一次訪問(wèn)節(jié)點(diǎn)時(shí)，輸出節(jié)點(diǎn)的值，然后進(jìn)行左子樹(shù)的遍歷
• 中序遍歷：在第二次訪問(wèn)節(jié)點(diǎn)時(shí)(即mostRight的右指針指向當(dāng)前節(jié)點(diǎn)時(shí))，輸出節(jié)點(diǎn)的值，然后進(jìn)行右子樹(shù)的遍歷
• 后序遍歷：后序遍歷的實(shí)現(xiàn)相對(duì)復(fù)雜，需要在遍歷過(guò)程中記錄左子樹(shù)最右分支的路徑，并在回溯時(shí)逆序輸出

4. 優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)：Morris遍歷的空間復(fù)雜度為O(1)，比使用?；蜻f歸的遍歷算法更高效
  此外，Morris遍歷不會(huì)占用額外的內(nèi)存空間，對(duì)于內(nèi)存受限的環(huán)境非常友好
• 缺點(diǎn)：Morris遍歷會(huì)修改原始樹(shù)的結(jié)構(gòu)，需要在遍歷完成后還原 此外，Morris遍歷的實(shí)現(xiàn)相對(duì)復(fù)雜，需要理解其背后的思想和原理

5. 應(yīng)用場(chǎng)景
Morris遍歷適用于需要高效遍歷二叉樹(shù)且內(nèi)存受限的場(chǎng)景
例如，在處理大規(guī)模數(shù)據(jù)時(shí)，使用Morris遍歷可以節(jié)省內(nèi)存空間并提高遍歷效率
同時(shí)，Morris遍歷也可以用于實(shí)現(xiàn)一些特殊的算法和數(shù)據(jù)結(jié)構(gòu)，如線索二叉樹(shù)等

102.二叉樹(shù)的層序遍歷

🌟BFS+隊(duì)列

原題鏈接

C++
若未特殊標(biāo)明，以下題解均寫用C++

方法一 BFS

/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};

方法二 隊(duì)列

/*** 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) {}* };*/
// #include <queue>  
// #include <vector>  
class Solution {  
public:  vector<vector<int>> levelOrder(TreeNode* root) {  vector<vector<int>> ans;  if (root == nullptr )return ans;  queue<TreeNode*> cur;  cur.push(root);  while (!cur.empty()) {// 當(dāng)前層的節(jié)點(diǎn)數(shù)int size = cur.size();// 存儲(chǔ)當(dāng)前層的節(jié)點(diǎn)值  vector<int> vals; for (int i = 0; i < size; ++i) {  TreeNode* node = cur.front();  cur.pop();vals.push_back(node->val);if (node->left)cur.push(node->left); if (node->right)cur.push(node->right);  }  ans.push_back(vals); // 將當(dāng)前層的節(jié)點(diǎn)值添加到答案中  }  return ans;  }
};