立志重刷代码随想录60天冲冲冲！！——第二十天

701.二叉搜索树中的插入操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            TreeNode* node = new TreeNode(val);
            return node;
        }

        if (root->val < val) {
            root->right = insertIntoBST(root->right, val);
        } else if (root->val > val) {
            root->left = insertIntoBST(root->left, val);
        }
        return root;
    }
};

450.删除二叉搜索树中的节点

最好手动释放内存。。当然，我没释放

class Solution {
public:
// 先找到删除的节点。然后分五种情况：没有找到删除节点、删除节点左右为空、左空右不空、左不空右空、左右都不空
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return NULL; // 没找到删除节点
        if (root->val == key) {
            if (root->left == nullptr && root->right == nullptr) return NULL; // 左右空
            else if (root->left != nullptr && root->right == nullptr) return root->left; //左不空，右空
            else if (root->left == nullptr && root->right != nullptr) return root->right; // 左空，右不空
            else // 左右都不空！！！
            {
                // 把左子树，移动到右子树的最左边
                TreeNode* cur = root->right;
                while (cur->left) {
                    cur = cur->left;
                }
                cur->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;
    }
};