LeetCode 987. 二叉树的垂序遍历

Categories:

题目描述
思路分析
1. 解法一：排序分组（推荐）
相似题目

题目描述

✅ 987. 二叉树的垂序遍历

思路分析

解法一：排序分组（推荐）

核心思路：

记录每个节点的坐标 (row, col)，根节点为 (0, 0)。

DFS 采集所有节点三元组 (col, row, val)。

先按列升序，再按行升序，最后按值升序排序，然后按列分组输出。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示节点数，排序主导。

空间复杂度：O(n)，用于存储节点信息与递归栈。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        dfs(root, 0, 0, nodes);

        nodes.sort((a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            }
            if (a[1] != b[1]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[2], b[2]);
        });

        List<List<Integer>> res = new ArrayList<>();
        Integer prevCol = null;
        for (int[] node : nodes) {
            if (prevCol == null || node[0] != prevCol) {
                res.add(new ArrayList<>());
                prevCol = node[0];
            }
            res.get(res.size() - 1).add(node[2]);
        }

        return res;
    }

    private void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
        if (node == null) {
            return;
        }

        nodes.add(new int[]{col, row, node.val});

        dfs(node.left, row + 1, col - 1, nodes);
        dfs(node.right, row + 1, col + 1, nodes);
    }
}

import "sort"

func verticalTraversal(root *TreeNode) [][]int {
	type item struct {
		col int
		row int
		val int
	}

	items := make([]item, 0)

	var dfs func(node *TreeNode, row, col int)
	dfs = func(node *TreeNode, row, col int) {
		if node == nil {
			return
		}

		items = append(items, item{col: col, row: row, val: node.Val})

		dfs(node.Left, row+1, col-1)
		dfs(node.Right, row+1, col+1)
	}

	dfs(root, 0, 0)

	sort.Slice(items, func(i, j int) bool {
		if items[i].col != items[j].col {
			return items[i].col < items[j].col
		}
		if items[i].row != items[j].row {
			return items[i].row < items[j].row
		}
		return items[i].val < items[j].val
	})

	res := make([][]int, 0)
	prevCol := 1 << 60
	for _, it := range items {
		if it.col != prevCol {
			res = append(res, []int{})
			prevCol = it.col
		}
		res[len(res)-1] = append(res[len(res)-1], it.val)
	}

	return res
}

相似题目

题目	难度	考察点
314. 二叉树的垂直遍历	中等	BFS/坐标
102. 二叉树的层序遍历	中等	BFS
103. 二叉树的锯齿形层序遍历	中等	BFS
987. 二叉树的垂序遍历	困难	排序分组
515. 在每个树行中找最大值	中等	层序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/34883774