当前位置：网站首页>力扣题解 二叉树（7）
力扣题解 二叉树（7）
2022-07-27 05:20:00 【RL-UAV】
105.从前序与中序遍历序列构造二叉树
总结：新题解 加 哈希表
二叉树的根节点就是前序序列的第一个节点，这样就可以把中序序列拆分成两部分，根节点前面就是左子树，后面就是右子树，那么就知道了左右子树的节点数量，依此就可以对前序序列也进行拆分，这样左右子树的前序、中序序列都知道了，递归构建左右子树就可以了。
/** * 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 {
unordered_map<int, int> pos;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) pos[inorder[i]] = i; //中序放在哈希表里头
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
if (pl > pr || il > ir) return nullptr;
int k = pos[preorder[pl]] - il; 中序的位置 - 前序第一个位置 左子树的位数
TreeNode* root = new TreeNode(preorder[pl]);
root->left = build(preorder, inorder, pl + 1, pl + k, il, il + k - 1); //全部的左子树 全部的中序左子树
root->right = build(preorder, inorder, pl + k + 1, pr, il + k + 1, ir);
return root;
}
};
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) return NULL;
int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
cout << "----------" << endl;
cout << "leftInorder :";
for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "rightInorder :";
for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "leftPreorder :";
for (int i = leftPreorderBegin; i < leftPreorderEnd; i++) {
cout << preorder[i] << " ";
}
cout << endl;
cout << "rightPreorder :";
for (int i = rightPreorderBegin; i < rightPreorderEnd; i++) {
cout << preorder[i] << " ";
}
cout << endl;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) return NULL;
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};
654.最大二叉树
class Solution {
private:
// 在左闭右开区间[left, right)，构造二叉树
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left >= right) return nullptr;
// 分割点下标：maxValueIndex
int maxValueIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
}
TreeNode* root = new TreeNode(nums[maxValueIndex]);
// 左闭右开：[left, maxValueIndex)
root->left = traversal(nums, left, maxValueIndex);
// 左闭右开：[maxValueIndex + 1, right)
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
617.合并二叉树
此时前序遍历，完整代码就写出来了，如下：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
// 修改了t1的数值和结构
t1->val += t2->val; // 中
t1->left = mergeTrees(t1->left, t2->left); // 左
t1->right = mergeTrees(t1->right, t2->right); // 右
return t1;
}
};
本题我们也使用队列，模拟的层序遍历，代码如下：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
queue<TreeNode*> que;
que.push(t1);
que.push(t2);
while(!que.empty()) {
TreeNode* node1 = que.front(); que.pop();
TreeNode* node2 = que.front(); que.pop();
// 此时两个节点一定不为空，val相加
node1->val += node2->val;
// 如果两棵树左节点都不为空，加入队列
if (node1->left != NULL && node2->left != NULL) {
que.push(node1->left);
que.push(node2->left);
}
// 如果两棵树右节点都不为空，加入队列
if (node1->right != NULL && node2->right != NULL) {
que.push(node1->right);
que.push(node2->right);
}
// 当t1的左节点 为空 t2左节点不为空，就赋值过去
if (node1->left == NULL && node2->left != NULL) {
node1->left = node2->left;
}
// 当t1的右节点 为空 t2右节点不为空，就赋值过去
if (node1->right == NULL && node2->right != NULL) {
node1->right = node2->right;
}
}
return t1;
}
};
700.二叉搜索树中的搜索
递归法：
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
if (root->val > val) return searchBST(root->left, val);
if (root->val < val) return searchBST(root->right, val);
return NULL;
}
};
迭代法：
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != NULL) {
if (root->val > val) root = root->left;
else if (root->val < val) root = root->right;
else return root;
}
return NULL;
}
};
98.验证二叉搜索树
总结：
中序遍历下，输出的二叉搜索树节点的数值是有序序列。
递归：
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == NULL) return;
traversal(root->left);
vec.push_back(root->val); // 将二叉搜索树转换为有序数组
traversal(root->right);
}
public:
bool isValidBST(TreeNode* root) {
vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
traversal(root);
for (int i = 1; i < vec.size(); i++) {
// 注意要小于等于，搜索树里不能有相同元素
if (vec[i] <= vec[i - 1]) return false;
}
return true;
}
};
迭代法中序遍历稍加改动就可以了，代码如下：
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = NULL; // 记录前一个节点
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left; // 左
} else {
cur = st.top(); // 中
st.pop();
if (pre != NULL && cur->val <= pre->val)
return false;
pre = cur; //保存前一个访问的结点
cur = cur->right; // 右
}
}
return true;
}
};
530.二叉搜索树的最小绝对差
递归
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == NULL) return;
traversal(root->left);
vec.push_back(root->val); // 将二叉搜索树转换为有序数组
traversal(root->right);
}
public:
int getMinimumDifference(TreeNode* root) {
vec.clear();
traversal(root);
if (vec.size() < 2) return 0;
int result = INT_MAX;
for (int i = 1; i < vec.size(); i++) {
// 统计有序数组的最小差值
result = min(result, vec[i] - vec[i-1]);
}
return result;
}
};
边栏推荐
- std::bind与std::function的一些应用
- [song] rebirth of me in py introductory training (9): exception handling
- Xmind 思维导图 2022 v12.0.3中文版更新了哪些内容？
- When multiple formulas in latex share a sequence number
- 判断是否为回文结构的三种方法
- 非重叠矩形中的随机点（力扣每日一题）
- 【头歌】重生之我在py入门实训中（5）：列表
- Baiwen driver Daquan learning (I) LCD driver
- What tools are needed to make video post effects?
- 李宏毅 2020 深度学习与人类语言处理 DLHLP-Conditional Generation by RNN and Attention-p22
猜你喜欢
浅记一下十大排序
Super remote connection management tool: Royal TSX
C＃ Json编码在TCP通讯中的一些使用总结
Matlab 画图（超详细）
Live Home 3D Pro interior home design tool
Lightroom Classic 2022 v11.4中文版「最新资源」
韦东山 数码相框 项目学习（四）简易的TXT文档显示器（电纸书）
能替代ps的修图软件？
arcgis for js api(2) 获取要素服务的id集合
Weidongshan digital photo frame project learning (IV) simple TXT document display (e-paper book)
随机推荐
力扣每日一题 剑指 Offer II 091. 粉刷房子
芯片、存储器及其关键指标简述 一
Weidongshan digital photo frame project learning (IV) simple TXT document display (e-paper book)
【头歌】重生之我在py入门实训中（2）：公式编程
力扣题解 动态规划（4）
超强远程连接管理工具：Royal TSX
李宏毅 2020 深度学习与人类语言处理 DLHLP-Coreference Resolution-p21
韦东山 数码相框 项目学习（四）简易的TXT文档显示器（电纸书）
【Unity URP】代码获取当前URP配置UniversalRendererData，并动态添加RendererFeature
服务器相关的指标解释
【头歌】重生之我在py入门实训中（8）： 模块
小技巧-彻底删除U盘中的文件
[first song] machine learning of rebirth - linear regression
编程学习记录——第5课【分支和循环语句】
c语言-线性顺序表
ps 2022 六月更新，都新增了哪些功能
【头歌】重生之我在py入门实训中（10）： Numpy
socket编程一：使用fork()实现最基础的并发模式
WebODM win10安装教程(亲测)
Super remote connection management tool: Royal TSX