树与堆

建堆从最后一个非叶节点往前做 siftDown，整体 O(n)：高度 h 的节点最多 n / 2^(h+1) 个，下沉代价 O(h)，求和收敛到 O(n)；逐个插入才是 O(n log n)。

function siftDown(a, i, n) {
    while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let max = i;
        if (l < n && a[l] > a[max]) max = l;
        if (r < n && a[r] > a[max]) max = r;
        if (max === i) break;
        [a[i], a[max]] = [a[max], a[i]];
        i = max;
    }
}

function heapSort(a) {
    for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i, a.length);
    for (let end = a.length - 1; end > 0; end--) {
        [a[0], a[end]] = [a[end], a[0]]; // 堆顶换到末尾
        siftDown(a, 0, end);
    }
    return a;
}

建堆 O(n)，每次取堆顶后下沉 O(log n)，共 n 次，整体 O(n log n)，原地排序、空间 O(1)。不稳定，交换会打乱相等元素的相对顺序。堆的真实用途：优先队列（任务调度、延时队列）、Top K（维护大小为 k 的堆）、Dijkstra 取最近节点、合并 K 个有序链表。

常见误区

很多人以为"BST 查找是 O(log n)"。 实际上只有平衡时才是；按升序插入会退化成链表，查找变 O(n)，这就是需要 AVL / 红黑树的原因。

很多人以为建堆和堆排序一样是 O(n log n)。 实际上自底向上建堆是 O(n)，因为绝大多数节点在底层、下沉距离很短，只有堆排序整体才是 O(n log n)。

常考题型

1. 二叉树的最大深度

思路：递归取左右子树较大值加一；深树改层序遍历数层数，避免栈溢出。

function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

时间 O(n)，空间 O(h)，h 为树高。易错点：空树返回 0 而不是 1。

2. 层序遍历

思路：队列里按层存节点，每轮先记下当前层长度，处理完这一层再进下一层。

function levelOrder(root) {
    if (!root) return [];
    const res = [], queue = [root];
    let head = 0; // 用头指针代替 shift，避免 O(n) 搬移
    while (head < queue.length) {
        const level = [];
        for (let i = queue.length - head; i > 0; i--) {
            const node = queue[head++];
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(level);
    }
    return res;
}

时间 O(n)，空间 O(n)。易错点：循环条件写成 queue.length 会边遍历边追加，层就乱了。

3. 验证二叉搜索树

思路：递归时把合法区间往下传，左子树收紧上界、右子树收紧下界。

function isValidBST(root, min = -Infinity, max = Infinity) {
    if (!root) return true;
    if (root.val <= min || root.val >= max) return false;
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

时间 O(n)，空间 O(h)。易错点：只比较父子节点会漏掉"孙子比爷爷大"；BST 不允许重复值时边界要用 <= / >=。

4. 数组中的第 K 大元素

思路：维护大小为 k 的小顶堆，堆顶是当前第 k 大，比堆顶小的元素直接丢弃。

function findKthLargest(nums, k) {
    const heap = [];
    for (const x of nums) {
        heap.push(x);
        let i = heap.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (heap[p] <= heap[i]) break;
            [heap[p], heap[i]] = [heap[i], heap[p]];
            i = p;
        }
        if (heap.length > k) {
            heap[0] = heap.pop();
            let j = 0;
            while (true) {
                const l = 2 * j + 1, r = l + 1;
                let m = j;
                if (l < heap.length && heap[l] < heap[m]) m = l;
                if (r < heap.length && heap[r] < heap[m]) m = r;
                if (m === j) break;
                [heap[j], heap[m]] = [heap[m], heap[j]];
                j = m;
            }
        }
    }
    return heap[0];
}

时间 O(n log k)，空间 O(k)。易错点：求第 K 大要用小顶堆；heap[0] = heap.pop() 之后必须重新下沉。

关联阅读

• 数组与链表：堆的底层就是数组，链表是树节点的另一种串法
• 栈与队列：DFS 用栈，BFS 用队列