LeetCode 314. 二叉树的垂直遍历

2024-08-28 HGNULB 约 5 分钟

文章信息 8 个分类 6 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 阿里快手

题目描述

✅ 314. 二叉树的垂直遍历

题意分析

将二叉树节点按列从左到右输出。每列内部按从上到下的顺序排列；同一行、同一列的多个节点，保留它们在树中从左到右的顺序，不按节点值排序。

给根节点列号 0，左孩子的列号减一，右孩子的列号加一。这样问题可以拆成两件事：按正确顺序访问节点，再把节点值放入对应列。

解法：BFS 按列分组

核心思路

[!blue]

BFS 使用先进先出的队列，先访问浅层，再访问深层，因此天然满足列内“从上到下”的要求。每次让左孩子先于右孩子入队，上一层父节点又已经按从左到右排列，所以下一层也会保持这个顺序，同层同列的节点无需另行排序。

队列中同时保存节点及其列号。节点出队时，直接把值追加到 colToValues[col]；因为出队顺序已经正确，分组只需保留插入顺序。

哈希表本身没有列号顺序，需要另外记录 minCol 与 maxCol，遍历结束后从最小列号到最大列号依次取出列表。列号不会出现中间整列缺失：从根到任意节点，每条边只让列号变化 1，到达两端的路径必然经过中间列。

普通 DFS 即使先左后右，也可能先访问某列的深层节点，再访问同列的浅层节点，所以不能直接用 DFS 的访问顺序填充结果。这里用 BFS 同时解决深度和同层顺序。

解题步骤

空树直接返回空结果；否则将根节点和列号 0 入队，初始化最小、最大列号为 0。

每次取出一个节点及对应列号，将节点值追加到该列列表，并更新列号范围。

左孩子存在时携带 col - 1 入队，随后让右孩子携带 col + 1 入队。

重复直到队列为空，再按 minCol..maxCol 顺序收集每列列表。

Java 的节点队列和列号队列必须同步入队、出队；Go 用一个结构体直接保存这两个信息。

代码实现

class Solution {
    // 题目要求同一列从上到下输出。
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Map<Integer, List<Integer>> colToValues = new HashMap<>();
        Queue<TreeNode> nodeQueue = new ArrayDeque<>();
        Queue<Integer> colQueue = new ArrayDeque<>();

        nodeQueue.offer(root);
        colQueue.offer(0);

        int minCol = 0;
        int maxCol = 0;

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            // 节点与列号必须始终成对取出
            int col = colQueue.poll();

            colToValues.computeIfAbsent(col, key -> new ArrayList<>()).add(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);

            // 左孩子先入队，保持同层同列节点的左右顺序
            if (node.left != null) {
                nodeQueue.offer(node.left);
                colQueue.offer(col - 1);
            }

            if (node.right != null) {
                nodeQueue.offer(node.right);
                colQueue.offer(col + 1);
            }
        }

        for (int col = minCol; col <= maxCol; col++) {
            res.add(colToValues.get(col));
        }

        return res;
    }
}

func verticalOrder(root *TreeNode) [][]int {
    // 题目要求同一列从上到下输出。
    res := make([][]int, 0)
    if root == nil {
        return res
    }

    type item struct {
        node *TreeNode
        col  int
    }

    colToValues := make(map[int][]int)
    queue := make([]item, 0)
    queue = append(queue, item{node: root, col: 0})
    minCol, maxCol := 0, 0

    for head := 0; head < len(queue); head++ {
        cur := queue[head]
        node := cur.node
        // 节点与列号必须始终成对取出
        col := cur.col

        colToValues[col] = append(colToValues[col], node.Val)
        if col < minCol {
            minCol = col
        }
        if col > maxCol {
            maxCol = col
        }

        // 左孩子先入队，保持同层同列节点的左右顺序
        if node.Left != nil {
            queue = append(queue, item{node: node.Left, col: col - 1})
        }
        if node.Right != nil {
            queue = append(queue, item{node: node.Right, col: col + 1})
        }
    }

    for col := minCol; col <= maxCol; col++ {
        res = append(res, colToValues[col])
    }
    return res
}

复杂度分析

时间复杂度：期望 $O(n)$，遍历与收集列均为线性，无需排序。

空间复杂度：$O(n)$，列分组与队列。

关键点总结

[!green]

BFS 决定每列内部的顺序，列号决定节点属于哪一组。

左孩子先入队，才能保留同一行内原有的左右顺序。

列号按连续整数遍历，避免依赖哈希表顺序，也无需额外排序。

易错点总结

[!yellow]

同行同列按原有左右顺序输出，不要误用其他垂序遍历题的“按节点值排序”规则。

不能直接遍历哈希表输出各列，哈希表的迭代顺序不代表从左到右。

节点与列号必须一一对应，平行队列的任意一次遗漏都会让后续分组错位。

先右后左入队会反转同层节点顺序；DFS 直接追加则可能破坏从上到下的顺序。

相似题目

题目	难度	关联与区别
987. 二叉树的垂序遍历	困难	列坐标定义相同，但原题对同一行列的节点还按值排序，本题保留层序到达顺序。
102. 二叉树的层序遍历	中等	BFS保证从上到下访问，再按列号分桶可保留同层从左到右的先后。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/42842114

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！