LeetCode 314. 二叉树的垂直遍历

Categories:

题目描述
思路分析
1. 解法一：BFS + 分列（推荐）
相似题目

题目描述

✅ 314. 二叉树的垂直遍历

思路分析

解法一：BFS + 分列（推荐）

核心思路：

BFS 过程中记录节点列号，按列分组。

使用哈希表保存列到节点值列表的映射。

记录最小列与最大列，按列输出。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，用于队列与哈希表。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Map<Integer, List<Integer>> map = 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();

            map.computeIfAbsent(col, k -> 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(map.get(col));
        }

        return res;
    }
}

func verticalOrder(root *TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}

	colMap := make(map[int][]int)
	nodeQueue := make([]*TreeNode, 0)
	colQueue := make([]int, 0)

	nodeQueue = append(nodeQueue, root)
	colQueue = append(colQueue, 0)

	minCol, maxCol := 0, 0
	for len(nodeQueue) > 0 {
		node := nodeQueue[0]
		nodeQueue = nodeQueue[1:]
		col := colQueue[0]
		colQueue = colQueue[1:]

		colMap[col] = append(colMap[col], node.Val)

		if col < minCol {
			minCol = col
		}
		if col > maxCol {
			maxCol = col
		}

		if node.Left != nil {
			nodeQueue = append(nodeQueue, node.Left)
			colQueue = append(colQueue, col-1)
		}
		if node.Right != nil {
			nodeQueue = append(nodeQueue, node.Right)
			colQueue = append(colQueue, col+1)
		}
	}

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

	return res
}

相似题目

题目	难度	考察点
987. 二叉树的垂序遍历	困难	排序
102. 二叉树的层序遍历	中等	BFS
103. 二叉树的锯齿形层序遍历	中等	BFS
515. 在每个树行中找最大值	中等	BFS
199. 二叉树的右视图	中等	BFS

本文作者: HGNULB

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