算法记录第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 与resultif(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;}