987. Vertical Order Traversal of a Binary Tree二叉树的垂直顺序遍历

 1import java.util.ArrayList;
 2import java.util.Collections;
 3import java.util.List;
 4import java.util.TreeMap;
 5
 6/**
 7 * @author lxn
 8 * @description 987. Vertical Order Traversal of a Binary Tree
 9 * @create 2020-03-16 23:49
10 */
11public class Algorithm987 {
12    public static void main(String[] args) {
13        TreeNode root = new TreeNode(3);
14        root.left = new TreeNode(9);
15        root.right = new TreeNode(20);
16        root.right.left = new TreeNode(15);
17        root.right.right = new TreeNode(7);
18        List<List<Integer>> res = new Solution987().verticalTraversal(root);
19    }
20}
21
22class Solution987 {
23    public List<List<Integer>> verticalTraversal(TreeNode root) {
24        // key: 同一x坐标 value: 键是同一深度的, 值是相同位置的点的集合
25        TreeMap<Integer, TreeMap<Integer, List<Integer>>> map = new TreeMap<>();
26        helper(root, 0, 0, map);
27        List<List<Integer>> res = new ArrayList<>();
28        int index = 0;
29
30        for (TreeMap<Integer, List<Integer>> cols : map.values()){
31            res.add(new ArrayList<>());
32            for (List<Integer> rows : cols.values()){ // 相同位置的点，按结点值从小到大返回
33                Collections.sort(rows);
34                for (int val : rows) res.get(index).add(val);
35            }
36            index++;
37        }
38        return res;
39    }
40
41    public void helper(TreeNode root, int index, int depth, TreeMap<Integer, TreeMap<Integer, List<Integer>>> map){
42        if (root == null) return;
43        if (!map.containsKey(index)){ // 该竖直方向上没出现过
44            map.put(index, new TreeMap<>());
45        }
46        if (!map.get(index).containsKey(depth)){ // 该深度没出现过
47            map.get(index).put(depth, new ArrayList<>());
48        }
49        map.get(index).get(depth).add(root.val); // 找出(index, depth)位置上的点，插入结点值
50
51        helper(root.left, index - 1, depth + 1, map); // 递归做结点
52        helper(root.right, index + 1, depth + 1, map); // 递归右结点
53    }
54}