修剪序列

[题目链接](https://www.nowcoder.com/practice/10f82ad64c454053aab7579c8b2e0c64)

思路

题意模拟：对一棵二叉树，每次从上到下、从左到右修剪节点。删除一个节点后，若其子树悬空（未接触地面），子树会因重力下落到地面。所有下落完成后再继续修剪，直到所有节点被删除。

关键观察：什么是"地面"

把二叉树画成上方是根、下方是叶的形式。地面就是原始树最深层所在的那一行（第 行， 为树高）。

当一个节点被删除后，其子树失去支撑，整棵子树保持形状不变地竖直下落，直到子树中最深的节点落到地面为止。设子树高度为 ，则子树根落在第 行（0-indexed）。

建模

每个节点在被加入"待修剪"集合时，都带有两个属性：

  1. 所在行（row）：决定"从上到下"的优先级；
  2. 原始列号（col）：决定同一行内"从左到右"的顺序。

列号用中序遍历序来赋值，这天然保持了左右相对位置不变——即使子树下落，节点之间的左右关系不会改变。

算法流程

  1. 预处理：DFS 计算每个节点的子树高度 以及中序列号 ，记总树高 。
  2. 优先队列（小根堆）：按 排序。初始将根节点以 入堆。
  3. 循环取堆顶：弹出 最小的节点，记入结果。对其左、右孩子分别计算落地行 ，压入堆中。
  4. 堆空时结束。

样例演示

以 {1,2,3,4,5,#,6,#,7} 为例，树高 ，地面在第 3 行。

步骤 弹出节点 row 释放子树 子树根落地行
1 1 0 2(h=3), 3(h=2) 2→行0, 3→行1
2 2 0 4(h=2), 5(h=1) 4→行1, 5→行2
3 4 1 7(h=1) 7→行2
4 3 1 6(h=1) 6→行2
5 7 2 — —
6 5 2 — —
7 6 2 — —

输出：，与题目一致。

复杂度

  • 时间复杂度：，每个节点入堆、出堆各一次。
  • 空间复杂度：，用于存储高度、列号和优先队列。

代码

class Solution {
public:
    vector<int> pruneSequence(TreeNode* root) {
        if (!root) return {};

        unordered_map<TreeNode*, int> ht, col;
        int colCnt = 0;

        // 计算子树高度
        function<int(TreeNode*)> getH = [&](TreeNode* u) -> int {
            if (!u) return 0;
            return ht[u] = 1 + max(getH(u->left), getH(u->right));
        };
        int H = getH(root);

        // 中序赋列号
        function<void(TreeNode*)> inorder = [&](TreeNode* u) {
            if (!u) return;
            inorder(u->left);
            col[u] = colCnt++;
            inorder(u->right);
        };
        inorder(root);

        // 小根堆 (row, col, node)
        using T = tuple<int, int, TreeNode*>;
        priority_queue<T, vector<T>, greater<T>> pq;
        pq.push({0, col[root], root});

        vector<int> res;
        while (!pq.empty()) {
            auto [r, c, u] = pq.top(); pq.pop();
            res.push_back(u->val);
            for (auto ch : {u->left, u->right}) {
                if (ch) pq.push({H - ht[ch], col[ch], ch});
            }
        }
        return res;
    }
};

import java.util.*;

public class Solution {
    private Map<TreeNode, Integer> ht = new HashMap<>();
    private Map<TreeNode, Integer> col = new HashMap<>();
    private int colCnt = 0;

    public int[] pruneSequence(TreeNode root) {
        if (root == null) return new int[0];

        int H = getH(root);
        inorder(root);

        // 小根堆 (row, col, nodeIndex)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
            a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        pq.offer(new int[]{0, col.get(root), 0});

        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            TreeNode u = nodes.get(top[2]);
            res.add(u.val);
            for (TreeNode ch : new TreeNode[]{u.left, u.right}) {
                if (ch != null) {
                    int idx = nodes.size();
                    nodes.add(ch);
                    pq.offer(new int[]{H - ht.get(ch), col.get(ch), idx});
                }
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    private int getH(TreeNode u) {
        if (u == null) return 0;
        int h = 1 + Math.max(getH(u.left), getH(u.right));
        ht.put(u, h);
        return h;
    }

    private void inorder(TreeNode u) {
        if (u == null) return;
        inorder(u.left);
        col.put(u, colCnt++);
        inorder(u.right);
    }
}

class Solution:
    def pruneSequence(self, root):
        if not root:
            return []
        import heapq

        ht, col = {}, {}
        cnt = [0]

        def get_h(u):
            if not u:
                return 0
            h = 1 + max(get_h(u.left), get_h(u.right))
            ht[id(u)] = h
            return h

        H = get_h(root)

        def inorder(u):
            if not u:
                return
            inorder(u.left)
            col[id(u)] = cnt[0]
            cnt[0] += 1
            inorder(u.right)

        inorder(root)

        heap = [(0, col[id(root)], id(root), root)]
        res = []
        while heap:
            r, c, _, u = heapq.heappop(heap)
            res.append(u.val)
            for ch in (u.left, u.right):
                if ch:
                    heapq.heappush(heap, (H - ht[id(ch)], col[id(ch)], id(ch), ch))
        return res

function pruneSequence(root) {
    if (!root) return [];

    const ht = new Map(), col = new Map();
    let colCnt = 0;

    function getH(u) {
        if (!u) return 0;
        const h = 1 + Math.max(getH(u.left), getH(u.right));
        ht.set(u, h);
        return h;
    }
    const H = getH(root);

    function inorder(u) {
        if (!u) return;
        inorder(u.left);
        col.set(u, colCnt++);
        inorder(u.right);
    }
    inorder(root);

    // 简易小根堆用排序数组模拟（节点数不大时足够）
    let pq = [[0, col.get(root), root]];
    const res = [];
    while (pq.length) {
        pq.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        const [r, c, u] = pq.shift();
        res.push(u.val);
        for (const ch of [u.left, u.right]) {
            if (ch) pq.push([H - ht.get(ch), col.get(ch), ch]);
        }
    }
    return res;
}
module.exports = { pruneSequence };