算法简记- BST相关

1、// 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

// 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

var insertIntoBST = function(root, 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;
};

2、// 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

var deleteNode = function(root, key) {
    if (!root) return null;
    if (root.val === key) {
        // 删除操作
        if (!root.left) {
            return root.right;
        }
        if (!root.right) {
            return root.left;
        }
        let minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);

    } else if (root.val < key) {

        root.right = deleteNode(root.right, key);
    } else if (root.val > key) {

        root.left = deleteNode(root.left, key);
    }
    return root;
};
let getMin = (node) => {
    while (node.left) {
        node = node.left;
    }
    return node;
}