二叉搜索树中的插入操作
力扣题目链接: 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
js
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
js
var insertIntoBST = function (root, val) {
let insertNode = new TreeNode(val);
function dfs(node) {
if (!node) return;
if (val > node.val) {
if (!node.right) node.right = insertNode;
else dfs(node.right);
} else {
if (!node.left) node.left = insertNode;
else dfs(node.left);
}
}
dfs(root);
return root || insertNode;
};
删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
根据二叉搜索树的性质
- 如果目标节点大于当前节点值，则去右子树中删除；
- 如果目标节点小于当前节点值，则去左子树中删除；
- 如果目标节点就是当前节点，分为以下三种情况：
- 其无左子：其右子顶替其位置，删除了该节点；
- 其无右子：其左子顶替其位置，删除了该节点；
- 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点
其左右子节点都有情况比较复杂，可以看动画实现：
js
var deleteNode = function (root, key) {
if (!root) return null;
if (key > root.val) root.right = deleteNode(root.right, key);
else if (key < root.val) root.left = deleteNode(root.left, key);
// 删除的是当前节点
else {
if (!root.left) return root.right;
else if (!root.right) return root.left;
else {
// 左右子树都存在的情况下
let newRoot = root.right;
// 找到右子树下的最左子树，将原本的 root.left 指向这个节点
let cur = root.right;
while (cur.left) {
cur = cur.left;
}
cur.left = root.left;
return newRoot;
}
}
return root;
};
修剪二叉搜索树
js
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
js
/**
* @param {TreeNode} root
* @param {number} low
* @param {number} high
* @return {TreeNode}
*/
var trimBST = function (root, low, high) {
if (!root) return null;
if (root.val < low) return trimBST(root.right, low, high);
else if (root.val > high) return trimBST(root.left, low, high);
else {
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
}
return root;
};
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
思路
题目中说要转换为一棵高度平衡二叉搜索树。这和转换为一棵普通二叉搜索树有什么差别呢？
其实这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取，所以想构成不平衡的二叉树是自找麻烦。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
将一个按照升序排列的有序数组：中序遍历，左根右，从小 ➡️ 大
- 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
- 最大值所在的下标左区间 构造左子树
- 最大值所在的下标右区间 构造右子树
代码
js
var sortedArrayToBST = function (nums) {
function buildTree(nums, l, r) {
if (l > r) return null;
let mid = (l + r) >>> 1;
let root = new TreeNode(nums[mid]);
root.left = buildTree(nums, l, mid - 1);
root.right = buildTree(nums, mid + 1, r);
return root;
}
return buildTree(nums, 0, nums.length - 1);
};