JAVA 13ms DFS Solution, TreeMap + PriorityQueue


  • 0

    BFS is simpler for this question. I provide a DFS solution here.
    Use the height and insert orders as the key for sorting the queue.

    public class Solution {
        class Ele implements Comparable<Ele>{
            int val;
            int h;
            int order;
            Ele(int val, int h, int order){
                this.val = val;
                this.h = h;
                this.order = order;
            }
            public int compareTo(Ele other){
                if(this.h == other.h){
                    return Integer.compare(this.order, other.order);
                }
                return Integer.compare(this.h, other.h);
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null)return res;
            Map<Integer, PriorityQueue<Ele>> map = new TreeMap<>();
            preOrder(root, map, 0, 0);
            for(Integer key:map.keySet()){
                PriorityQueue<Ele> tmp = map.get(key);
                List<Integer> tmpList = new ArrayList<Integer>();
                while(!tmp.isEmpty()){
                    tmpList.add(tmp.poll().val);
                }
                res.add(tmpList);
            }
            return res;
        }
        public void preOrder(TreeNode root, Map<Integer, PriorityQueue<Ele>> map, int key, int height){
            if(root == null)return;
            if(map.containsKey(key)){
                PriorityQueue<Ele> tmp = map.get(key);
                tmp.add(new Ele(root.val,height,tmp.size()));
            }else{
                PriorityQueue<Ele> tmp = new PriorityQueue<Ele>();
                tmp.add(new Ele(root.val,height,1));
                map.put(key, tmp);
            }
            preOrder(root.left, map, key-1, height+1);
            preOrder(root.right, map, key+1, height+1);
        }
    }
    

  • 0
    J

    Did you pass all tests? I got one wrong. I think the expected result is wrong.

    for test:
    [-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

    there's one column, my answer is
    [3,-44,-60,12,-51,-59,67,-88,48,-26,92,72]
    the expected answer is:
    [3,-44,-60,12,-59,-51,67,-88,48,-26,92,72]


  • 0

    @jobhunting88 I did pass all the tests, otherwise I won't post it. I think there maybe some tiny error in your code. The input order matters (when two nodes the same height), previously I didn't store the order and I failed.

    The output from my code:

    [[-4,78,73,-77,-54,-36],[12,-51,-81,4,8,3,-30,-33,86,81,98,24],[-64,-53,-31,47,-35,-67,-37,72,-4,-38,-31,-31,-18,-66,-72,43],[18,-93,33,-51,-38,47,-24,-11,80,44,-91,-42,-40,70,-93],[76,3,-64,26,-31,-19,10,-85,-96,67,34,-92,-1],[3,-44,-60,12,-59,-51,67,-88,48,-26,92,72],[53,-81,27,60,-55,-70,72,56,-88,-98,-84],[11,-49,-90,90,-34,-27,-67,98],[74,17,-17,-65,-53,39],[37]]


Log in to reply
 

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