235. 二叉搜索树的最近公共祖先
这个刷题训练营很好的一点是昨天做过的题，今天会有类似的让你加深记忆。就像是这道题，昨天我是看会了，但是自己没动手写。今天就有些不会做了。condition什么的还是有点没弄明白。还得动手啊。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root == NULL) || (root->val == p->val) || (root->val == q->val)){
return root;
}
TreeNode* found_p = lowestCommonAncestor(root->left,p,q);;
TreeNode* found_q = lowestCommonAncestor(root->right,p,q);;
if((found_p!=NULL) && (found_q!=NULL)){
return root;
}
if((found_p==NULL) && (found_q!=NULL)){
return found_q;
}
if((found_p!=NULL) && (found_q==NULL)){
return found_p;
}
else{
return NULL;
}
}
};
701二叉搜索树中的插入操作
由于这道题并不需要把二叉搜索树整理得漂漂亮亮的，所以我的逻辑就是找到可以放置的最底层的根节点就塞进去。
class Solution {
public:
TreeNode* pre;
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == nullptr){
TreeNode* new_node = new TreeNode(val);
if(pre == nullptr){
return new_node;
}
else{
if(pre->val > val){
pre->left = new_node;
}
else{
pre->right = new_node;
}
return root;
}
}
pre = root;
if(root->val > val){
insertIntoBST(root->left,val);
}
else{
insertIntoBST(root->right,val);
}
return root;
}
};
我看了下之前跟着Carl写的解法，比我的要简介很多。他是把递归return的数据直接赋值给了当前的left or right。不用像我一样还记录了之前一个treenode。看来我对递归的返回值利用得还是不好。
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;
}
};
450删除二叉搜索树中的节点
之前就做过，这回又做了一遍。这题的难点就是分析出五种情况。
- 没找到与key对应的节点
- 该节点没有左右子节点（这样第二简单，直接删除就行）
- 该节点没有右子节点。那就把当前节点删了，把左子节点换上去
- 该子节点没有左节点。那就把右子节点换上去
- 左右子节点都有。那就得把当前左子树移动到右子树上最左的根节点下面。
上面的2-5需要背一下处理方法。自己想的话可能想得不清楚，会总觉得按照上面这个方式处理会出错。这道题还需要再做即便才行。其实并不难，就是要记住这五种情况。以及要把结果传递到根节点的左或右节点上。这点也十分重要。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == nullptr){
return root;
}
if(root->val == key){
if((root->left == nullptr) && (root->right == nullptr)){
delete root;
return nullptr;
}
else if((root->left != nullptr) && (root->right == nullptr)){
TreeNode* temp = root->left;
delete root;
return temp;
}
else if((root->left == nullptr) && (root->right != nullptr)){
TreeNode* temp = root->right;
delete root;
return temp;
}
else{
TreeNode* cur = root->right;
while(cur->left!=nullptr){
cur = cur->left;
}
cur->left = root->left;
TreeNode* temp = root;
root = root->right;
delete temp;
return root;
}
}
if(root->val > key){
root->left = deleteNode(root->left,key);
}
if(root->val < key){
root->right = deleteNode(root->right,key);
}
return root;
}
};
