Java Straight forward solution with a designed data structure


  • 0

    I design a data structure BigNode to keep record of both nodes and its relative position in the result. With BFSing the given tree, I can summary the structure and write it to a TreeMap(the reason for using TreeMap is it can sort the input automatically). In the end, what I only need to do it transfer every key-value pair in TreeMap to the result ArrayList;
    (I also write a print function to help you debug the program with the RunCode function)

    class BigNode{
            TreeNode node;
            int pos;
            BigNode(TreeNode node, int pos){
                this.node = node;
                this.pos = pos;
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null) return res;
            
            BigNode node = new BigNode(root, 0);
            TreeMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
            Queue<BigNode> queue = new LinkedList<BigNode>();
            
            queue.offer(node);
            while(!queue.isEmpty()){
                int levelNum = queue.size();
                for(int i = 0; i < levelNum; i ++){
                    BigNode tmp = queue.peek();
                    if(queue.peek().node.left != null){
                        BigNode left = new BigNode(tmp.node.left, tmp.pos - 1);
                        queue.offer(left);
                    }
                    if(queue.peek().node.right != null){
                        BigNode right = new BigNode(tmp.node.right, tmp.pos + 1);
                        queue.offer(right);
                    }
                    if(map.containsKey(queue.peek().pos)){
                        map.get(queue.peek().pos).add(queue.peek().node.val);
                    }else{
                        List<Integer> cur = new ArrayList<Integer>();
                        cur.add(queue.peek().node.val);
                        map.put(queue.peek().pos, cur);
                    }
                    queue.poll();
                }
            }
            print(map);
            
            for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
                res.add(entry.getValue());
            }
            return res;
        }
        /*
        public void print(TreeMap<Integer, List<Integer>> map){
            for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
                int key = entry.getKey();
                List<Integer> value = entry.getValue();
                System.out.print(key + "      ");
                for(int val : value){
                    System.out.print(val + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
        */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.