hacktoberfest2019-leetcode/Java/987_Vertical_Order_Traversal_of_a_Binary_Tree.java at master · manasec/hacktoberfest2019-leetcode · GitHub

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Question link https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        TreeMap<Integer, List<Integer>> verticalTraversalTreeMap = new TreeMap<>();
        TreeMap<Integer, TreeMap<Integer, List<Integer>>> verticalTraversalWithAdditionConditionTreeMap =
                new TreeMap<>();

        verticalTraversalUtilWithAdditionCondition(root, verticalTraversalWithAdditionConditionTreeMap, 0, 0);
        List<List<Integer>> result = new ArrayList<>();
        for (Map.Entry<Integer, TreeMap<Integer, List<Integer>>> entry : verticalTraversalWithAdditionConditionTreeMap.entrySet())  {
            TreeMap<Integer, List<Integer>> treeMap = entry.getValue();
            List<Integer> listLevel = new ArrayList<>();
            for (Map.Entry<Integer, List<Integer>> entry1 : treeMap.entrySet()) {
                List<Integer> list = entry1.getValue();
                Collections.sort(list);
                listLevel.addAll(list);
            }
            result.add(listLevel);
        }
        return result;
    }

    private void verticalTraversalUtilWithAdditionCondition(TreeNode root,
                                                            TreeMap<Integer, TreeMap<Integer, List<Integer>>> verticalTraversalWithAdditionConditionTreeMap,
                                                            int distanceFromOriginAlongXaxis, int level) {

        if (root == null) return;
        if (verticalTraversalWithAdditionConditionTreeMap.get(distanceFromOriginAlongXaxis) == null) {
            TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>();
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            treeMap.put(level, list);
            verticalTraversalWithAdditionConditionTreeMap.put(distanceFromOriginAlongXaxis, treeMap);
        } else {
            TreeMap<Integer, List<Integer>> treeMap =
                    verticalTraversalWithAdditionConditionTreeMap.get(distanceFromOriginAlongXaxis);

            if (treeMap.get(level) == null) {
                List<Integer> list = new ArrayList<>();
                list.add(root.val);
                treeMap.put(level, list);
            } else {
                List<Integer> list = treeMap.get(level);
                list.add(root.val);
                treeMap.put(level, list);
                verticalTraversalWithAdditionConditionTreeMap.put(distanceFromOriginAlongXaxis, treeMap);
            }
            verticalTraversalWithAdditionConditionTreeMap.put(distanceFromOriginAlongXaxis, treeMap);
        }
        verticalTraversalUtilWithAdditionCondition(root.left, verticalTraversalWithAdditionConditionTreeMap,
                distanceFromOriginAlongXaxis - 1, level + 1);
        verticalTraversalUtilWithAdditionCondition(root.right, verticalTraversalWithAdditionConditionTreeMap,
                distanceFromOriginAlongXaxis + 1, level + 1);
    }
}