代码随想录算法训练营第二十天|二叉树 part7

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {root = new TreeNode(val);return root;}if (root->val < val)root->right = insertIntoBST(root->right, val);if (root->val > val)root->left = insertIntoBST(root->left, val);return root;}
};

这一题比插入操作要难，因为会改变二叉搜索树的结构，并且不能违反二叉搜索树的特性。
当root就是要删除的元素时，分为3种情况：

1. root是叶子节点，返回null
2. root只有左子树或右子树，返回左子树或右子树
3. root左右子树都不为空。将root左子树移到右子树的最左端，返回右子树。
   递归处理左子树和右子树。

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)return nullptr;else if (root->left != nullptr && root->right == nullptr) return root->left;else if (root->left == nullptr && root->right != nullptr)return root->right;else {TreeNode* tmp = root->right;while (tmp->left) {tmp = tmp->left;} tmp->left = root->left;return root->right;}}if (key < root->val)root->left = deleteNode(root->left, key);if (key > root->val)root->right = deleteNode(root->right, key);return root;}
};