目录
- 一、二叉搜索树的最近公共祖先-LeetCode 235
- 思路
- 实现代码
- 个人问题
- 总结
- 二、二叉搜索树的插入操作-LeetCode 701
- 思路
- 实现代码
- 需要返回值
- 不需要返回值
- 个人问题
- 总结
- 三.删除二叉搜索树的节点-LeeCode 450
- 思路
- 实现代码
- 个人问题
- 总结
一、二叉搜索树的最近公共祖先-LeetCode 235
Leecode链接: leetcode 235
文章链接: 代码随想录
视频链接: B站
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
示例:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
思路
这道题其实跟那道二叉树最近公共祖先类似,有取巧的地方,即:题目要求需要找最近的祖先,那就直接找第一个处于两个节点值之间的节点,该节点一定是公共祖先直接返回该节点即可,至于为什么第一个一定是公共祖先,这是搜索树的性质决定的。这是题目没有告诉的规律,需要自己理解。
实现代码
//cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr;
if(root->val > q->val && root->val > p->val){
TreeNode* left_c = lowestCommonAncestor(root->left,p,q);
return left_c;
}
if(root->val < q->val && root->val < p->val){
TreeNode* right_c = lowestCommonAncestor(root->right,p,q);
return right_c;
}
return root;
}
};
个人问题
没有想到这种解题思路,未写出代码。
总结
比较简单虽然代码不多,但需要对二叉搜索树的特性比较了解才能写出代码。
二、二叉搜索树的插入操作-LeetCode 701
Leecode链接: LeetCode 701
文章链接: 代码随想录
视频链接: B站
给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
示例:
输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:
思路
跟递归遍历搜索树类似,需要插入的值比当前值小就往左子树走,反之往右子树走,遇到空节点创建新节点并返回新节点的指针然后接住即可。如果递归函数不要返回值,那就要保存父节点指针。
实现代码
需要返回值
//cpp
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==NULL){
TreeNode* Node = new TreeNode(val);
return Node;
}
if(val<root->val) root->left = insertIntoBST(root->left,val);
if(val>root->val) root->right = insertIntoBST(root->right,val);
return root;
}
};
不需要返回值
//cpp
class Solution {
private:
TreeNode* parent;
void traversal(TreeNode* cur, int val) {
if (cur == NULL) {
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);
return;
}
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
parent = new TreeNode(0);
if (root == NULL) {
root = new TreeNode(val);
}
traversal(root, val);
return root;
}
};
个人问题
个人开始使用无参数递归,但发现比较难写,使用有参数后直接代码通过。
总结
简单题,本体没有具体递归的遍历顺序,所以中间节点没什么需要做的事情可以空不写内容。
三.删除二叉搜索树的节点-LeeCode 450
Leecode链接: LeetCode 450
文章链接: 代码随想录
视频链接: B站
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
示例:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
思路
题目就是找节点然后删除节点,如果没找到节点,则返回root;如果找到节点且为叶子节点,那就直接返回空节点,因为删掉了返回给父节点的孩子节点肯定为null嘛;如果找到节点不为叶子节点:1.左右孩子都不为空,那就让左孩子节点换到右孩子最左下的位置。2.其中有任意孩子节点为空,那就返回那个不为空的孩子节点给父节点接住。
实现代码
//cpp
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == NULL) return NULL;
if(key>root->val) root->right = deleteNode(root->right,key);
if(key<root->val) root->left = deleteNode(root->left,key);
if(root->val == key){
if(root->right && !root->left){
return root->right;
}
else if(!root->right && root->left){
return root->left;
}
else if(!root->right && !root->left){
return nullptr;
}
else if(root->left && root->right){
TreeNode* n = root->right;
while(n->left){
n = n->left;
}
n->left = root->left;
return root->right;
}
}
return root;
}
};
个人问题
编写代码时在处理左右孩子都不为空时不知道怎么处理,到底是该右孩子直接顶替还是左孩子顶替。
总结
总体难度偏中等,需要考虑的情况虽然多但是都比较容易想到,主要还是代码实现上思维有局限。遍历顺序似乎没那么重要,个人用的后序,卡哥用的前序。