leetcode_day22

本文最后更新于 2024年6月13日 上午

今日任务:

235. 二叉搜索树的最近公共祖先

与day21的第三题相比,这题多了二叉搜索树这一条件,变得更简单

题目:

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

思路

主体思路就是当root的值在p和q之间时,root就是最近公共祖先了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p || root == q || !root) return root;//沿用236题的返回条件
if(p->val > q->val) {//先设定p < q
TreeNode * temp = p;
p = q;
q = temp;
}
if(p->val < root->val && root->val < q->val) return root;//如果root在之间,返回
if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);//不然就在左子树
else return lowestCommonAncestor(root->right, p, q);//不然就在右子树
}
};

701. 二叉搜索树的插入操作

题目:

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

思路

不要拘泥于AVL的标准,这只是普通的二叉搜索树,哪怕退化成链都没关系,所以直接在最底部插入就行

然后问题转化为: 在二叉搜索树BST中查找val。当然肯定找不到,但最后会在某个叶子节点处下行碰到null,那么只需要判断走没走到叶子,以及val该插在叶子的左边还是右边

别想着在中途插入了,本菜比卡了一个小时没写出来,看评论区全是“伪装成medium的easy”😭

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root) {
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;
}
};

450. 删除二叉搜索树中的节点

题目:

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  • 首先找到需要删除的节点;
  • 如果找到了,删除它。

思路:

依然别想着AVL的左右旋什么的,别自己给自己上难度,简单暴力地分类讨论就行:

  1. 没找到val(root是空的),返回nullptr
  2. 要删的是个叶子,直接删了返回nullptr
  3. 要删的节点只有一个孩子,删完孩子上来补位,返回这个独生子
  4. 要删的节点有两个孩子,把左子树接到右子树最左边的节点下面当左孩子(这样可以最简单地使树依然合法)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return root;

if(root->val < key) root->right = deleteNode(root->right, key);
if(root->val > key) root->left = deleteNode(root->left, key);
if(root->val == key) {
if(!root->left && !root->right) {
delete root;
return nullptr;
}
else if(root->left && !root->right) {
TreeNode * temp = root->left;
delete root;
return temp;
}
else if(root->right && !root->left) {
TreeNode * temp = root->right;
delete root;
return temp;
}
else{
TreeNode * keeper = root->right;
while(keeper->left != nullptr) keeper = keeper->left;
keeper->left = root->left;
TreeNode * temp = root->right;
delete root;
return temp;
}
}
return root;
}
};

leetcode_day22
https://novelyear.github.io/2024/06/13/leetcode-day22/
作者
Leoo Yann
更新于
2024年6月13日
许可协议