LC.P987[二叉树的垂序遍历]

题目描述

给你二叉树的根结点 root，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例1

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列 1 ：只有结点 20 在此列中。
列 2 ：只有结点 7 在此列中。

示例2

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。

示例3

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

  • 树中结点数目总数在范围 [1, 1000] 内
  • 0 <= Node.val <= 1000

思路

按照题目要求，自定义排序：将节点遍历，先按照列号从小到大排列，若列号相同，则按照行号从小到大排列，若同行同列，则按照值从小到大排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    List<int[]> list = new ArrayList<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, 0, 0);
        list.sort((a, b) -> {
            if (a[1] != b[1]) return a[1] - b[1]; // 列号从小到大
            else if (a[0] != b[0]) return a[0] - b[0]; // 同列节点，行号从小到大
            else return a[2] - b[2]; // 同行同列节点，按值从小到大
        });
        int lastCol = Integer.MIN_VALUE, index = -1;
        for (int[] cur : list) {
            int col = cur[1], val = cur[2];
            if (col != lastCol) {
                lastCol = col;
                ans.add(new ArrayList<>());
                ++index;
            }
            ans.get(index).add(val);
        }
        return ans;
    }

    private void dfs(TreeNode node, int row, int col) {
        if (node == null) return;
        list.add(new int[]{row, col, node.val});
        dfs(node.left, row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$