【散刷】二叉树基础OJ题（三）

📝前言说明：
本专栏主要记录本人的基础算法学习以及刷题记录，使用语言为C++。
每道题我会给出LeetCode上的题号（如果有题号），题目，以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解，主要是个人见解，如有不正确，欢迎指正，一起进步！

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C++学习笔记，C语言入门基础，python入门基础，python刷题专栏，Linux
🎀CSDN主页愚润泽

题目

LCR 155. 将二叉搜索树转化为排序的双向链表
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

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;}
};