当前位置：网站首页>力扣题解 二叉树（8）
力扣题解 二叉树（8）
2022-07-27 05:20:00 【RL-UAV】
501.二叉搜索树中的众数
class Solution {
private:
int maxCount; // 最大频率
int count; // 统计频率
TreeNode* pre;
vector<int> result;
void searchBST(TreeNode* cur) {
if (cur == NULL) return ;
searchBST(cur->left); // 左
// 中
if (pre == NULL) {
// 第一个节点
count = 1;
} else if (pre->val == cur->val) {
// 与前一个节点数值相同
count++;
} else {
// 与前一个节点数值不同
count = 1;
}
pre = cur; // 更新上一个节点
if (count == maxCount) {
// 如果和最大值相同，放进result中
result.push_back(cur->val);
}
if (count > maxCount) {
// 如果计数大于最大值频率
maxCount = count; // 更新最大频率
result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
result.push_back(cur->val);
}
searchBST(cur->right); // 右
return ;
}
public:
vector<int> findMode(TreeNode* root) {
count = 0;
maxCount = 0;
TreeNode* pre = NULL; // 记录前一个节点
result.clear();
searchBST(root);
return result;
}
};
236. 二叉树的最近公共祖先
总结：
忘了给自己定义TreeNode* left = 了。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else {
// (left == NULL && right == NULL)
return NULL;
}
}
};
稍加精简，代码如下：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL) return right;
return left;
}
};
235. 二叉搜索树的最近公共祖先
利用有序顺序排列：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
} else return root;
}
};
迭代代码如下：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root) {
if (root->val > p->val && root->val > q->val) {
root = root->left;
} else if (root->val < p->val && root->val < q->val) {
root = root->right;
} else return root;
}
return NULL;
}
};
701.二叉搜索树中的插入操作
总结：都是先建立一个新的节点，在比较大小。
迭代：
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
迭代：
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
TreeNode* cur = root;
TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
while (cur != NULL) {
parent = cur;
if (cur->val > val) cur = cur->left;
else cur = cur->right;
}
TreeNode* node = new TreeNode(val);
if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值
else parent->right = node;
return root;
}
};
450.删除二叉搜索树中的节点
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
if (root->val == key) {
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
if (root->left == nullptr && root->right == nullptr) {
///! 内存释放
delete root;
return nullptr;
}
// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
else if (root->left == nullptr) {
auto retNode = root->right;
///! 内存释放
delete root;
return retNode;
}
// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
else if (root->right == nullptr) {
auto retNode = root->left;
///! 内存释放
delete root;
return retNode;
}
// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
else {
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
TreeNode* tmp = root; // 把root节点保存一下，下面来删除
root = root->right; // 返回旧root的右孩子作为新root
delete tmp; // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key) {
if (root->right == nullptr) {
// 这里第二次操作目标值：最终删除的作用
return root->left;
}
TreeNode *cur = root->right;
while (cur->left) {
cur = cur->left;
}
swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
迭代法
删除节点的迭代法还是复杂一些的，但其本质我在递归法里都介绍了，最关键就是删除节点的操作（动画模拟的过程）
代码如下：
class Solution {
private:
// 将目标节点（删除节点）的左子树放到 目标节点的右子树的最左面节点的左孩子位置上
// 并返回目标节点右孩子为新的根节点
// 是动画里模拟的过程
TreeNode* deleteOneNode(TreeNode* target) {
if (target == nullptr) return target;
if (target->right == nullptr) return target->left;
TreeNode* cur = target->right;
while (cur->left) {
cur = cur->left;
}
cur->left = target->left;
return target->right;
}
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
TreeNode* cur = root;
TreeNode* pre = nullptr; // 记录cur的父节点，用来删除cur
while (cur) {
if (cur->val == key) break;
pre = cur;
if (cur->val > key) cur = cur->left;
else cur = cur->right;
}
if (pre == nullptr) {
// 如果搜索树只有头结点
return deleteOneNode(cur);
}
// pre 要知道是删左孩子还是右孩子
if (pre->left && pre->left->val == key) {
pre->left = deleteOneNode(cur);
}
if (pre->right && pre->right->val == key) {
pre->right = deleteOneNode(cur);
}
return root;
}
};
669. 修剪二叉搜索树
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
if (root->val < low) return trimBST(root->right, low, high);
if (root->val > high) return trimBST(root->left, low, high);
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
108.将有序数组转换为二叉搜索树
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子。
总结：
传出的节点，用当前节点左孩子接住，root->left = traversal(nums, left, mid - 1);
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
538.把二叉搜索树转换为累加树
右中左
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* cur) {
// 右中左遍历
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
边栏推荐
- arcgis for js api(2) 获取要素服务的id集合
- 【12】理解电路：从电报机到门电路，我们如何做到“千里传信”？
- std::bind与std::function的一些应用
- geonode geoserver win10 安装教程(亲测)
- [song] rebirth of me in py introductory training (9): exception handling
- 服务器相关的指标解释
- 2022.6.10 stm32mp157 serial port clock learning
- Gbase 8C - SQL reference 6 SQL syntax (12)
- socket编程一：使用fork()实现最基础的并发模式
- 浅记一下十大排序
猜你喜欢
Speech and Language Processing (3rd ed. draft) Chapter 2 ——正则表达式，文本归一化，编辑距离 阅读笔记
17. Attenuation of momentum and learning rate
15. GPU acceleration, Minist test practice and visdom visualization
11. Gradient derivation of perceptron
What has been updated in the Chinese version of XMIND mind map 2022 v12.0.3?
Xmind 思维导图 2022 v12.0.3中文版更新了哪些内容？
AE 3D particle system plug-in: Trapcode particle
浅记一下十大排序
![[high concurrency] interviewer](/img/50/baa662cb4ce30cf2ef4cb5952960dd.jpg)
[high concurrency] interviewer
Super remote connection management tool: Royal TSX
随机推荐
个人开发者申请代码签名证书的签发流程
编程学习记录——第5课【分支和循环语句】
Weidongshan digital photo frame project learning (III) transplantation of freetype
韦东山 数码相框 项目学习（四）简易的TXT文档显示器（电纸书）
方差与协方差
韦东山 数码相框 项目学习（二）在LCD上显示中文字符
面试常问Future、FutureTask和CompletableFuture
[first song] deep learning of rebirth -keras (elementary)
【头歌】重生之CNN图片分类基础
芯片、存储器及其关键指标简述 一
【头歌】重生之我在py入门实训中（10）： Numpy
【Arduino】重生之Arduino 学僧（1）
安全帽反光衣检测识别数据集和yolov5模型
【头歌】重生之我在py入门实训中（9）：异常处理
pytorch转onnx相关问题
STM32 infrared remote control
A photo breaks through the face recognition system: you can nod your head and open your mouth, netizens
【头歌】重生之机器学习-线性回归
[first song] rebirth of me in py introductory training (2): formula programming
百问网驱动大全学习（二）I2C驱动