235. 二叉搜索树的最近公共祖先
- 题目链接：235. 二叉搜索树的最近公共祖先
- 思路：和二叉树的最近公共祖先类似，这里根据二叉树搜索树的特性可以提前判断，如果p,q在root节点值的左右两边，则答案就是root，不是的话，p,q要么就在root的左边，要么就在root的右边
- 代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL || root == p || root == q) return root; // 确定为rootif((root->val > p->val && root->val < q->val) || (root->val < p->val && root->val > q->val))return root;if(root->val > q->val) // 确定在左边return lowestCommonAncestor(root->left, p, q);else // 确定在右边return lowestCommonAncestor(root->right, p, q);}
};
701.二叉搜索树中的插入操作
- 题目链接：701.二叉搜索树中的插入操作
- 思路：根据二叉搜索树特性，插入的节点只能是叶子节点，直接根据val值遍历，最终插入即可
- 代码：
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 //if(root->val < val)root->right = insertIntoBST(root->right, val);return root;}
};
450.删除二叉搜索树中的节点
- 题目链接：450.删除二叉搜索树中的节点
- 思路：遍历二叉树，找到对应节点，然后删除当前节点，让当前节点的右节点往上移一步，当前节点的左子树移到，当前节点的右子树的左子树的最底层的最左边的节点当左子树
- 代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(!root)return nullptr;if(root->val == key) {if(!root->right)return root->left;if(!root->left)return root->right; // 没有左右子树其中一个，另外一个顶上TreeNode* node = root->right; while (node->left) node = node->left;node->left = root->left; root = root->right;} else if(root->val > key) {root->left = deleteNode(root->left, key);} else {root->right = deleteNode(root->right, key);}return root;}
};
