5ms Java Clean Solution


  • 142

    The following solution takes 5ms.

    • BFS, put node, col into queue at the same time
    • Every left child access col - 1 while right child col + 1
    • This maps node into different col buckets
    • Get col boundary min and max on the fly
    • Retrieve result from cols

    Note that TreeMap version takes 9ms.


    Here is an example of [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Notice that every child access changes one column bucket id. So 12 actually goes ahead of 11.

    vertical by yavinci on 500px.com


    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
    
        q.add(root); 
        cols.add(0);
    
        int min = 0;
        int max = 0;
        
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = cols.poll();
            
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(node.val);
    
            if (node.left != null) {
                q.add(node.left); 
                cols.add(col - 1);
                min = Math.min(min, col - 1);
            }
            
            if (node.right != null) {
                q.add(node.right);
                cols.add(col + 1);
                max = Math.max(max, col + 1);
            }
        }
    
        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
    
        return res;
    }
    

    Alternatively, we can calculate the rang first, then insert into buckets. Credit to @Jinx_boom


    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> cols = new ArrayList<>();
        if (root == null) {
            return cols;
        }
        
        int[] range = new int[] {0, 0};
        getRange(root, range, 0);
        
        for (int i = range[0]; i <= range[1]; i++) {
            cols.add(new ArrayList<Integer>());
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> colQueue = new LinkedList<>();
        
        queue.add(root);
        colQueue.add(-range[0]);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int col = colQueue.poll();
            
            cols.get(col).add(node.val);
            
            if (node.left != null) {
                queue.add(node.left);   
                colQueue.add(col - 1);
            } 
            if (node.right != null) {
                queue.add(node.right);
                colQueue.add(col + 1);
            }
        }
        
        return cols;
    }
    
    public void getRange(TreeNode root, int[] range, int col) {
        if (root == null) {
            return;
        }
        range[0] = Math.min(range[0], col);
        range[1] = Math.max(range[1], col);
        
        getRange(root.left, range, col - 1);
        getRange(root.right, range, col + 1);
    }

  • 9
    D

    Similar idea with TreeMap.

    public int index = 0;
    public TreeMap<Integer, List<Integer>> tm;
    
    public class Pair {
        TreeNode node;
        int index;
        public Pair(TreeNode n, int i) {
            node = n;
            index = i;
        }
    }
    
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        tm = new TreeMap<Integer, List<Integer>>();
        if (root == null) return res;
        
        Queue<Pair> q = new LinkedList<Pair>();
        q.offer(new Pair(root, 0));
        
        while (!q.isEmpty()) {
            Pair cur = q.poll();
            if (!tm.containsKey(cur.index)) tm.put(cur.index, new ArrayList<Integer>());
            tm.get(cur.index).add(cur.node.val);
            
            if (cur.node.left != null) q.offer(new Pair(cur.node.left, cur.index-1));
            if (cur.node.right != null) q.offer(new Pair(cur.node.right, cur.index+1));
        }
        
        for (int key : tm.keySet()) res.add(tm.get(key));
        return res;
    }

  • 0
    N

    It seems your algorithm is not right. Given a perfect 4-level binary tree, named by level: 1; 2,3; 4,5,6,7; 8,9,10,11,12,13,14,15, I got this result: [[8], [4], [2, 9, 10, 12], [1, 5, 6], [3, 11, 13, 14], [7], [15]]. See 12 runs into a bucket ahead of 11's. I don't think that's right. The correct answer should be [[8],[4],[2,9,10],[5],[1,11,12],[6],[3,13,14],[7],[15]]. Draw the tree on a paper, you'll see.


  • 1

    @nick46, thanks for your question. It is correct. At first I had the same confusion as you. 12 do appear on the left of 11. By saying vertical order, IMO, each node at each level has the same width, please see my updated post for more clarification.


  • 8
    G

    Also a bit subtle is why the problem requires a BFS instead of say DFS(which is what I tried).
    @yavinci It would be worth mentioning in the explanation that since the nodes in a column are ordered by their row number(depth) we cannot process level x+2 nodes before we process level x.
    If you do DFS, the result has the same List<Integer> elements but in the wrong order.


  • 11
    W

    cpp solution using BFS.

    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> res;
            if(!root) return res;
            map<int,vector<int>> hm;
            queue<pair<TreeNode*,int>> q;
            q.push({root,0});
            while(!q.empty()){
                TreeNode* node=q.front().first;
                int col=q.front().second;
                q.pop();
                hm[col].push_back(node->val);
                if(node->left) q.push({node->left,col-1});
                if(node->right) q.push({node->right,col+1});
            }
            for(auto i:hm){
                res.push_back(i.second);
            }
        return res;
    }
    

    };


  • 0
    R

    Definitely one of the smartest and cleanest solution, with detailed explanations I've ever seen on LC.
    Thx for sharing


  • 0
    D

    Thanks for bringing up the problem with DFS. I was wondering why can't we use DFS.


  • 0

    Memory Limit Exceeded


  • 7
    M

    Useful tip for Java 8 users:

    if(!map.containsKey(col)) map.put(col, new ArrayList<Integer>());

    can be replaced with:

    map.putIfAbsent(col, new ArrayList<>());


  • 0
    L

    Similar idea, integrate the node and corresponding col num into a new class.

    class Node {
        TreeNode node;
        int col;
        public Node(TreeNode node, int col) {
            this.node = node;
            this.col = col;
        }
    }
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null)   return res;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(root, 0));
            Map<Integer, List<Integer>> map = new HashMap<>();
            int min = 0, max = 0;
            while (!queue.isEmpty()) {
                Node cur = queue.poll();
                // update map
                if (!map.containsKey(cur.col))  map.put(cur.col, new ArrayList<Integer>());
                map.get(cur.col).add(cur.node.val);
                
                if (cur.node.left != null) {
                    queue.offer(new Node(cur.node.left, cur.col-1));
                    min = Math.min(cur.col-1, min);
                }
                if (cur.node.right != null) {
                    queue.offer(new Node(cur.node.right, cur.col+1));
                    max = Math.max(cur.col+1, max);
                }
            }
            // iterate the map
            for (int i = min; i <= max; i++) {
                res.add(map.get(i));
            }
            return res;
        }
    }
    

  • 3

    @darrenxyli Very smart idea! I'm confused about what is vertical order for a while... The last for-loop seems to be redundant, right? Since TreeMap.values() will return a view in ascending order. Thanks for your sharing!

        public List<List<Integer>> verticalOrder(TreeNode root) {
            Map<Integer,List<Integer>> idxNode = new TreeMap<>();
            Queue<Pair> q = new LinkedList<>();
            if (root != null) q.offer(new Pair(0, root));
            while (!q.isEmpty()) {
                Pair p = q.poll();
                if (!idxNode.containsKey(p.idx))
                    idxNode.put(p.idx, new ArrayList<>());
                idxNode.get(p.idx).add(p.node.val);
    
                if (p.node.left != null) q.offer(new Pair(p.idx - 1, p.node.left));
                if (p.node.right != null) q.offer(new Pair(p.idx + 1, p.node.right));
            }
            return new ArrayList<>(idxNode.values());
        }
    

    ps: I realize that the time complexity will be O(NlogN) using TreeMap sadly... So I change my mind to use HashMap in order to maintain O(N) time.

        public List<List<Integer>> verticalOrder(TreeNode root) {
            Map<Integer,List<Integer>> colNode = new HashMap<>();
            Queue<Pair> q = new LinkedList<>();
            if (root != null) q.offer(new Pair(0, root));
            int min = 0, max = 0;
            while (!q.isEmpty()) {
                Pair p = q.poll();
                if (!colNode.containsKey(p.col))
                    colNode.put(p.col, new ArrayList<>());
                colNode.get(p.col).add(p.node.val);
                min = Math.min(min, p.col);
                max = Math.max(max, p.col);
    
                if (p.node.left != null) q.offer(new Pair(p.col - 1, p.node.left));
                if (p.node.right != null) q.offer(new Pair(p.col + 1, p.node.right));
            }
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = min; i <= max; i++) ret.add(colNode.get(i));
            return ret;
        }
    

  • 0

    Please anyone put @yavinci 's explanation of width into this question's description field.

    Much appreciated!


  • 0
    E

    I believe we don't need to calculate min and max anyway

    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new LinkedList<List<Integer>>();
            if(root==null) return res;
            
            Map<Integer,List<Integer>> map = new HashMap<>();
            Queue<TreeNode> nodeQueue = new LinkedList<>();
            Queue<Integer> levelQueue = new LinkedList<>();
            
            nodeQueue.offer(root);
            levelQueue.offer(0);
            while(!nodeQueue.isEmpty()){
                TreeNode node = nodeQueue.poll();
                int level = levelQueue.poll();
                if(!map.containsKey(level)){
                    List<Integer> list = new LinkedList<>();
                    map.put(level,list);
                    if(level<0) res.add(0,list);
                    else res.add(list);
                }
                map.get(level).add(node.val);
                if(node.left!=null){
                    nodeQueue.offer(node.left);
                    levelQueue.offer(level-1);
                }
                if(node.right!=null){
                    nodeQueue.offer(node.right);
                    levelQueue.offer(level+1);
                }
            }
            return res;
        }
    }
    

  • 0
    H

    Very Clean Code!!!!!!!


  • 0
    J

    Can I use stack instead of queue?


  • 0

    @jessebest It's level based traversal, you'd better use queue. If you want to use stack, you can implement queue with stack also, which is another question in LeetCode. :)


  • 0
    M

    @wei_fy
    Thanks for the nice code! FWIW, the transform from hm to res can move the items over instead of copying:

    for(auto& i : hm)
        res.push_back(move(i.second));
    

  • 0
    L

    The following solution does not pass the test below (because of the order of 8 and 2).
    Can anyone help me to understand what I did wrong please?

    Input:
    [3,9,8,4,0,1,7,null,null,null,2,5]
    Output:
    [[4],[9,5],[3,0,1],[2,8],[7]]
    Expected:
    [[4],[9,5],[3,0,1],[8,2],[7]]

    public List<List<Integer>> verticalOrder(TreeNode root) {
            Map<Integer,List<Integer>> map = new TreeMap<Integer, List<Integer>>();
            verticalOrderHelper(root,map,0);
            List<List<Integer>> result = new ArrayList<List<Integer>>(map.values());
            return result;
        }
        
        public void verticalOrderHelper(TreeNode root,Map<Integer,List<Integer>> map,Integer level){
    		if (root == null) return;
    		List<Integer> list = map.get(level);
    		if (list==null)
    			list = new ArrayList<Integer>();
    		list.add(root.val);
    		map.put(level, list);
    		verticalOrderHelper(root.left,map,level-1);
    		verticalOrderHelper(root.right,map,level+1);
    	}
    

  • 0
    U

    My Javascript version:

    const verticalOrder = (root) => {
        if (root === null) return [];
        let [min, max] = getRange(root, [0, 0], 0);
        let queue = [];
        let result = Array(max - min + 1).fill().map(() => Array());
        queue.push([0, root]);
        while(queue.length !== 0) {
            let [curIdx, curNode] = queue.shift();
            result[curIdx - min].push(curNode.val);
            curNode.left !== null && queue.push([curIdx - 1, curNode.left]);
            curNode.right !== null && queue.push([curIdx + 1, curNode.right]);
        }
        return result;
    };
    
    const getRange = (root, range, col) => {
      if (root === null) {
          return range;
      }
      range = [Math.min(range[0], col), Math.max(range[1], col)];
      range = getRange(root.left, range, col-1);
      range = getRange(root.right, range, col+1);
      return range;
    };
    

Log in to reply
 

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