LeetCode二叉树的垂序遍历

题目描述

给你二叉树的根结点 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 在此列中。

987. 二叉树的垂序遍历

解题思路

首先本题是一道困难题，其解决方法并不难想，主要难度主要集中在实现的细节。对于相同列的排序，行小的在前，同行的按照从大到小排序，所以这个实现我想到了java的排序器，制定类的规则。这个问题想好就按照dfs进行一次遍历，主要记录行列，将同列的放入同一个List从而进行排序，整体实现思路并不复杂，主要需要看清楚题意并认真实现。

具体实现，代码如下

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<Node>> map = new HashMap<>();
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(0, 0, root, map, list);
        Collections.sort(list);//进行排序
        for (int i : list) {
            Collections.sort(map.get(i));
            List<Integer> l = new ArrayList<>();
            for (Node n : map.get(i))
                l.add(n.val);
            lists.add(l);
        }
        return lists;
    }

    public void dfs(int c, int r, TreeNode p, Map<Integer, List<Node>> map, List<Integer> list) {
        if (p != null) {
            if (!map.containsKey(c)) {
                list.add(c);
                map.put(c, new ArrayList<Node>());
            }
            map.get(c).add(new Node(r, p.val));
            dfs(c - 1, r + 1, p.left, map, list);
            dfs(c + 1, r + 1, p.right, map, list);
        }
    }
}

class Node implements Comparable<Node> {
    int r;
    int val;

    Node(int r, int val) {
        this.r = r;
        this.val = val;
    }

    public int compareTo(Node o) {//排序器
        if (this.r > o.r) {
            return 1;
        } else if (this.r < o.r) {
            return -1;
        } else {
            if (this.val > o.val)
                return 1;
            else if (this.val < o.val)
                return -1;
            else
                return 0;
        }
    }
}