Java DFS Solution with TreeMap


  • 0
    P
    public List<List<Integer>> verticalOrder(TreeNode root) {
            TreeMap<Integer, TreeMap<Integer, List<Integer>>> tmap = new TreeMap<>();
            dfs(root, 0, 0, tmap);
            
            List<List<Integer>> res = new ArrayList<>();
            
            for(TreeMap<Integer, List<Integer>> col : tmap.values()){
                List<Integer> list = new ArrayList<>();
                for(List<Integer> v : col.values()){
                    list.addAll(v);
                }
                res.add(list);
            }
            return res;
        }
        
        private void dfs(TreeNode node, int depth, int col, TreeMap<Integer, TreeMap<Integer, List<Integer>>> tmap){
            if(node == null)return;
            
            TreeMap<Integer, List<Integer>> cMap = tmap.getOrDefault(col, new TreeMap<Integer, List<Integer>>());
            List<Integer> list = cMap.getOrDefault(depth, new ArrayList<Integer>());
            list.add(node.val);
            cMap.put(depth, list);
            tmap.put(col, cMap);
            dfs(node.left, depth+1, col-1, tmap);
            dfs(node.right, depth+1, col+1, tmap);
               
        } 
    
    

Log in to reply
 

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