二叉搜索树的最近公共祖先
[https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html#算法公开课]
解法
没用二叉搜索树的性质，和之前普通二叉树的解法一样，就当复习了，挺妙的方法
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root || root == p || root == q) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left && right) return root;else if(left && !right) return left;else if(!left && right) return right;else return nullptr;}
};
二叉搜索树中的插入操作
[https://programmercarl.com/0701.二叉搜索树中的插入操作.html]
解法
顺着往下找，找到空的直接插入就行，不会出现需要插入的地方有别的节点的。
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(!root){return new TreeNode(val);}if(root->val > val){root->left = insertIntoBST(root->left,val);}else{root->right = insertIntoBST(root->right,val);}return root;}
};
删除二叉搜索树中的节点
[https://programmercarl.com/0450.删除二叉搜索树中的节点.html]
解法
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(!root) return root;if(root->val > key){root->left = deleteNode(root->left,key);return root;}else if(root->val < key){root->right = deleteNode(root->right,key);return root;}else{if(!root->right && !root->left) return nullptr;else if(!root->right) return root->left;else if(!root->left) return root->right;else{TreeNode* target = root->right;while(target->left){target = target->left;}root->right = deleteNode(root->right,target->val);target->right = root->right;target->left = root->left;return target;}}}
};