二分搜索树

private boolean search(TreeNode node, int val) {
    if (node == null) return false;
    if (val == node.val) return true;
    return val < node.val ? search(node.left, val) : search(node.right, val);
}

private TreeNode insert(TreeNode node, int val) {
    if (node == null) return new TreeNode(val);
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;   // 注意：重复值不插入（取决于业务）
}

private TreeNode delete(TreeNode node, int val) {
    if (node == null) return null;
    if (val < node.val) node.left = delete(node.left, val);
    else if (val > node.val) node.right = delete(node.right, val);
    else {
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        // 两个孩子：用中序后继（右子树最小）替代
        TreeNode successor = findMin(node.right);
        successor.right = deleteMin(node.right);
        successor.left = node.left;
        return successor;
    }
    return node;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

private TreeNode deleteMin(TreeNode node) {
    if (node.left == null) return node.right;
    node.left = deleteMin(node.left);
    return node;
}

// 前序：根 → 左 → 右
void preOrder(TreeNode n) {
    if (n == null) return;
    visit(n);
    preOrder(n.left);
    preOrder(n.right);
}

// 中序：左 → 根 → 右   → BST 得到升序
void inOrder(TreeNode n) {
    if (n == null) return;
    inOrder(n.left);
    visit(n);
    inOrder(n.right);
}

// 后序：左 → 右 → 根   → 子树信息收集
void postOrder(TreeNode n) {
    if (n == null) return;
    postOrder(n.left);
    postOrder(n.right);
    visit(n);
}

void levelOrder(TreeNode root) {
    if (root == null) return;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode u = q.poll();
        visit(u);
        if (u.left != null) q.offer(u.left);
        if (u.right != null) q.offer(u.right);
    }
}

// 方法 1：中序遍历，计数器
int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        if (--k == 0) return cur.val;
        cur = cur.right;
    }
    return -1;
}

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode n, long min, long max) {
    if (n == null) return true;
    if (n.val <= min || n.val >= max) return false;
    return validate(n.left, min, n.val) && validate(n.right, n.val, max);
}

int rangeSumBST(TreeNode root, int L, int R) {
    if (root == null) return 0;
    if (root.val < L) return rangeSumBST(root.right, L, R);
    if (root.val > R) return rangeSumBST(root.left, L, R);
    return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
}

int sum = 0;
TreeNode convertBST(TreeNode root) {
    if (root != null) {
        convertBST(root.right);          // 右 → 中 → 左（中序倒序）
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
    }
    return root;
}

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "C"); map.put(1, "A"); map.put(2, "B");

map.firstKey();      // 1
map.lastKey();       // 3
map.ceilingKey(2);   // 2  (≥ 2 的最小键)
map.floorKey(2);     // 2  (≤ 2 的最大键)
map.subMap(1, 3);    // {1, 2} (范围视图)