235. 二叉搜索树的最近公共祖先
思路
在二叉树公共祖先问题中，可以通过后序遍历，从二叉树节点向上遍历，找到最近公共祖先。本题中我们可以利用二叉搜索树的特性对这个问题进行简化。
从根节点向下搜索，我们遇到的第一个在[p,q]之间的节点就是二叉树的最近公共祖先。这个结论第一次做很难想出来。
1.我们从根节点开始遍历；
2.如果节点的的值大于p和q，p和q节点在该节点的左子树上，同理，如果节点的值小于p和q，那么p和q节点在该节点的右子树上。
3.如果第一次节点在p和q之间，说明这是两条路径的分岔路口，为最小公共祖先。
实现
点击查看代码
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root){
if(root->val > p->val && root->val > q->val){
root = root->left;
}
else if(root->val < p->val && root->val < q->val){
root = root->right;
}
else return root;
}
return NULL;
}
};
复杂度分析
- 时间复杂度：O(n)，n为二叉树的节点个数
- 空间复杂度：O(1)，没有额外的栈开销
701. 二叉搜索树中的插入操作
思路：模拟
二叉搜索树的左子树上所有节点的值都比该节点小，右子树上所有节点的值都比该节点的值大。因此
- 如果一个节点的左右子树不为空，那么可以将值插入到他的左右子树中
- 如果一个节点的左右子树有空子树，那么新建一个节点并将链接到他的父节点。
实现
点击查看代码
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == nullptr){
root = new TreeNode(val);
return root;
}
if(root->val > val) root->left = insertIntoBST(root->left, val);
if(root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
复杂度分析
- 时间复杂度：O(n)，当为链表时，n为其节点数
- 空间复杂度：O(n)
450. 删除二叉搜索树中的节点
思路：递归
1.当前节点为空时，返回nullptr；
2.当前节点的值小于目标值时，递归右子树
3.当前节点的值大于目标值时，递归左子树
4.当前节点等于目标值时
- 当前节点无子节点，直接返回
- 左子节点为空，右子节点不为空，将右子树作为新的子树，返回他的右子节点
- 右子节点为空，左子节点不为空，将左子树作为新的子树，返回他的左子节点
- 如果左右子节点都不为空，递归右子树，找到右子树最小节点，将当前节点的左子节点作为右子树最小节点的左子节点，将右子树作为新的子树，返回他的右子节点。
实现
点击查看代码
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == nullptr) return nullptr;
if(root->val == key){
if(root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
else if(root->left == nullptr && root->right != nullptr) {
cout<< "a" << endl;
TreeNode* temp = root;
root = root->right;
delete temp;
return root;;
}
else if(root->left != nullptr && root->right == nullptr) {
TreeNode* temp = root;
root = root->left;
delete temp;
return root;
}
else {
TreeNode* cur = root->right;
while(cur->left){
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;
}
};
复杂度分析
- 时间复杂度：O(n)，最差情况下
- 空间复杂度：O(n)