📝前言說明：
本專欄主要記錄本人的基礎算法學習以及刷題記錄，使用語言為C++。
每道題我會給出LeetCode上的題號（如果有題號），題目，以及最后通過的代碼。沒有題號的題目大多來自牛客網。對于題目的講解，主要是個人見解，如有不正確，歡迎指正，一起進步！

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C++學習筆記，C語言入門基礎，python入門基礎，python刷題專欄，Linux
🎀CSDN主頁 愚潤澤

LCR 155. 將二叉搜索樹轉化為排序的雙向鏈表

題目鏈接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/

• 中序遍歷，得到的序列是有序的
• 記錄當前節點的前一個節點 prev
• cur -> left = prev
• 但是 cur -> right 要指向 nxt（下一個節點）
• 我們可以讓 cur 當上一層的下一個節點，然后讓：pre -> right = cur

class Solution {
public:void dfs(Node* cur, Node* &prev) // 必須要按引用傳遞，要是全局的{if(!cur) return;dfs(cur->left, prev);cur->left = prev;if(prev)prev->right = cur;prev = cur;dfs(cur->right, prev);}Node* treeToDoublyList(Node* root) {if(root == nullptr) return nullptr;Node* prev = nullptr;dfs(root, prev);Node* tail = prev; // 遍歷完 prev 就是尾節點，nullptr 是最后一個節點退出// 找到頭節點（最左節點）Node* head = root;while (head->left) {head = head->left;}head->left = tail;tail->right = head;return head;}
};

105. 從前序與中序遍歷序列構造二叉樹

題目鏈接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 通過前序確定根，然后找到中序根的位置，可以劃分數的左右子樹// 然后再對左右子樹用同樣的方法，得到構建好的左右子樹// 遞歸時，子樹的 preorder 和 inorder 的區間會改變）if(preorder.empty()) return nullptr;// 左子樹的中序遍歷序列的元素個數（同時也是先序遍歷的, 因為左子樹遍歷完了才會遍歷右子樹）int left_size = ranges::find(inorder, preorder[0]) - inorder.begin();// 構造左子樹的 preorder 和 inordervector<int> l_pre(preorder.begin() + 1, preorder.begin() + 1 + left_size);vector<int> l_ino(inorder.begin(), inorder.begin() + left_size);// 構造右子樹的vector<int> r_pre(preorder.begin() + 1 + left_size, preorder.end());vector<int> r_ino(inorder.begin() + left_size + 1, inorder.end());TreeNode* left = buildTree(l_pre, l_ino); // 相信你把左子樹構建好了TreeNode* right = buildTree(r_pre, r_ino);return new TreeNode(preorder[0], left, right); // 用當前的根節點 + 構建好的左右子樹}
};

• 注意好迭代器的起始和結束位置的選擇（迭代器構造是左閉右開），注意要跳過根節點

106. 從中序與后序遍歷序列構造二叉樹

題目鏈接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = postorder.size();if(!n) return nullptr;int l_size = ranges::find(inorder, postorder[n - 1]) - inorder.begin();vector<int> l_pos(postorder.begin(), postorder.begin() + l_size);vector<int> l_ino(inorder.begin(), inorder.begin() + l_size);vector<int> r_pos(postorder.begin() + l_size, postorder.end() - 1);vector<int> r_ino(inorder.begin() + l_size + 1, inorder.end());TreeNode* left = buildTree(l_ino, l_pos);TreeNode* right = buildTree(r_ino, r_pos);return new TreeNode(postorder[n - 1], left, right);}
};

144. 二叉樹的前序遍歷

題目鏈接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

class Solution {
public:vector<int> ans;void dfs(TreeNode* root){if(!root) return;ans.push_back(root->val);dfs(root->left);dfs(root->right);}vector<int> preorderTraversal(TreeNode* root) {dfs(root);return ans;}
};

94. 二叉樹的中序遍歷

題目鏈接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

class Solution {
public:vector<int> ans;void dfs(TreeNode* root){if(!root) return;dfs(root->left);ans.push_back(root->val);dfs(root->right);}vector<int> inorderTraversal(TreeNode* root) {dfs(root);return ans;}
};

145. 二叉樹的后序遍歷

題目鏈接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

class Solution {
public:vector<int> ans;void dfs(TreeNode* root){if(!root) return;dfs(root->left);dfs(root->right);ans.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {dfs(root);return ans;}
};

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！