AC DFS Java, 15ms...


  • 0
    O

    Tagged each node with its level, and after a dfs traverse, do a Collections.sort to each indexed list of nodes. Pretty slow, but just for fum :)
    Also, please let me know if there's any improvement can be done to this piece of code.

    public class Solution {
        class IndexedNode implements Comparable<IndexedNode> {
            TreeNode node;
            int level;
            public IndexedNode(TreeNode node, int level) {
                this.node = node; this.level = level;
            }
    		@Override
    		public int compareTo(IndexedNode other) {
    			return this.level - other.level;
    		}
        }
        
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if (root == null) return ret;
            Map<Integer, List<IndexedNode>> map = new TreeMap<Integer, List<IndexedNode>>();
            helper(root, 0, 0, map);
            for (int key: map.keySet()) {
            	List<IndexedNode> cur = map.get(key);
            	Collections.sort(cur);
            	List<Integer> ans = new ArrayList<Integer>();
            	for (IndexedNode n: cur) ans.add(n.node.val);
            	ret.add(ans);
            }
            return ret;
        }
        
        public void helper(TreeNode node, int level, int idx, Map<Integer, List<IndexedNode>> map) {
            if (node == null) return;
            IndexedNode cur = new IndexedNode(node, level);
            if (!map.containsKey(idx)) map.put(idx, new ArrayList<IndexedNode>());
            map.get(idx).add(cur);
            helper(node.left, level + 1, idx - 1, map);
            helper(node.right, level + 1, idx + 1, map);
        }
    }
    

Log in to reply
 

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