Leaky Cauldron
0%

二叉树的垂直遍历

Posted on Edited on

题目(LeetCode #314)

给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。

如果两个结点在同一行和列，那么顺序则为 从左到右。

示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: [[9],[3,15],[20],[7]]

示例 2:

输入: root = [3,9,8,4,0,1,7]
输出: [[4],[9],[3,0,1],[8],[7]]

示例 3

输入: root = [3,9,8,4,0,1,7,null,null,null,2,5]
输出: [[4],[9,5],[3,0,1],[8,2],[7]]

提示:

  • 树中结点的数目在范围 [0, 100] 内.
  • -100 <= Node.val <= 100

题解

分别保存每个节点相对 root 节点的偏移层数，即每访问一次左子树就对其父节点偏移层数减 1，每访问一次右子树就加 1。在返回的 List 中按层数从小到大排序即可。

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
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();

        // 使用 TreeMap 保证按 key 排序
        Map<Integer, List<Integer>> res = new TreeMap<>();
        Map<TreeNode, Integer> nodeMap = new HashMap<>();
        nodeMap.put(root, 0);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            int i = nodeMap.get(curNode);

            res.computeIfAbsent(i, k -> new ArrayList<>()).add(curNode.val);
            if (curNode.left != null) {
                queue.add(curNode.left);
                nodeMap.put(curNode.left, i - 1);
            }

            if (curNode.right != null) {
                queue.add(curNode.right);
                nodeMap.put(curNode.right, i + 1);
            }
        }

        return new ArrayList<>(res.values());
    }
}