代码随想录打卡DAY20
算法记录第20天 [二叉树]
1.LeetCode 501. 二叉搜索树中的众数
题目描述：
- 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
- 如果树中有不止一个众数，可以按 任意顺序 返回。
- 假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
- 示例 1：
输入：root = [1,null,2,2]
输出：[2]
题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
解题步骤 ：
-
递归过程：
- 中序遍历：首先递归访问左子树，然后处理当前节点，最后递归访问右子树。
pre存储了上一个访问的节点，这样我们就可以比较当前节点和上一个节点的值。如果它们相同，则count增加；如果不同，则count重置为 1。
-
更新结果：
- 每次遇到新的节点时，检查它的出现频率。
- 如果它的频率等于当前
maxCount，则将其加入result。 - 如果它的频率大于
maxCount，则更新maxCount并清空result，重新添加当前节点值。
-
最终结果：遍历完树后，
result包含了所有出现次数最多的值。
代码：
int count=1;
int maxCount=1;
TreeNode* pre=nullptr;
vector<int> result;
void travseral(TreeNode* cur){
// 退出条件
if(cur==nullptr) return;
travseral(cur->left);
// 判断是否和pre相同 count++
if(pre==nullptr){
count=1;
}else if(pre->val == cur->val){
count++;
}else{
count=1;
}
// 判断maxCount 与result
if(count==maxCount){
result.push_back(cur->val);
}
if(count>maxCount){
maxCount=count;
result.clear();
result.push_back(cur->val);
}
// 递归
pre = cur;
travseral(cur->right);
}
vector<int> findMode(TreeNode* root) {
travseral(root);
return result;
}
2.LeetCode 701. 二叉搜索树中的插入操作
题目描述：
- 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
- 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
- 示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
题目链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/
解题步骤 ：
-
递归终止条件：如果当前节点为空 (
root == nullptr)，我们就创建一个新的节点并返回它。 -
递归过程：
- 如果
val小于当前节点的值 (val < root->val)，我们将递归地向左子树插入。 - 如果
val大于当前节点的值 (val > root->val)，我们将递归地向右子树插入。
- 如果
-
返回根节点：每次递归返回的根节点会更新其父节点的
left或right指针，从而维持树的结构。
代码：
TreeNode* parent;
void traversal(TreeNode* cur,int val){
// 返回条件，插入节点
if(cur==nullptr){
TreeNode* Node = new TreeNode(val);
if (val > parent->val) parent->right = Node;
else parent->left = Node;
return;
}
//
parent = cur;
if(cur->val > val) traversal(cur->left,val);
if(cur->val < val) traversal(cur->right,val);
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
parent = new TreeNode(0);
if (root == NULL) {
root = new TreeNode(val);
}
traversal(root, val);
return root;
}
3.LeetCode
题目描述：450. 删除二叉搜索树中的节点
- 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
- 一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/description/
解题步骤 ：
-
递归终止条件：
- 如果当前节点为空 (
root == nullptr)，表示没有找到要删除的节点，直接返回nullptr。
- 如果当前节点为空 (
-
找到了要删除的节点：
- 当
root->val == key时，表示当前节点就是需要删除的节点。此时需要根据当前节点的子树情况采取不同的删除策略。
- 当
-
删除节点的不同情况：
- 没有子节点（叶节点）：如果当前节点没有左孩子和右孩子，直接删除节点并返回
nullptr。 - 只有右孩子：如果当前节点没有左孩子，但有右孩子，删除当前节点，并将其右孩子替代当前节点。
- 只有左孩子：如果当前节点没有右孩子，但有左孩子，删除当前节点，并将其左孩子替代当前节点。
- 左右孩子都不为空：如果当前节点既有左子树又有右子树，那么需要找到右子树中的最小节点（即右子树中最左边的节点），用这个节点替代当前节点的值，并删除右子树中的最小节点。
- 没有子节点（叶节点）：如果当前节点没有左孩子和右孩子，直接删除节点并返回
-
递归删除：
- 如果当前节点的值大于
key，则递归删除左子树中的节点。 - 如果当前节点的值小于
key，则递归删除右子树中的节点。
- 如果当前节点的值大于
-
返回更新后的树：
- 在递归的每一步中，都需要返回更新后的根节点，以便正确维护树的结构。
代码：
TreeNode* deleteNode(TreeNode* root, int key) {
//1、没找到
if(root==nullptr) return root;
// 找到了删除的节点
if(root->val == key){
//2、左右孩子节点都空
if(!root->left && !root->right){
//! 内存释放
delete root;
return nullptr;
}
//3、左孩子节点空，右孩子节点不空
else if(!root->left ){
auto retNode = root->right;
//! 内存释放
delete root;
return retNode;
}
//4、右孩子节点不空，左孩子节点空
else if(!root->right){
auto retNode = root->left;
//! 内存释放
delete root;
return retNode;
}
// 5都不空
else{
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left;
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}