Implementation with BFS and TreeMap


  • 0
    T
    public class Solution {
        // BST and PowerNode which wraps up TreeNode and index of column.
        // the idea similar to finding top view of a binary tree
        // http://algorithms.tutorialhorizon.com/print-the-top-view-of-a-binary-tree/
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> listSet = new ArrayList<List<Integer>>();
            if (root == null) {
                return listSet;
            }
            
            Queue<PowerNode> queue = new LinkedList<PowerNode>();
            Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
            queue.add(new PowerNode(0, root));
            
            while (!queue.isEmpty()) {
                PowerNode pnode = queue.poll();
                if (!map.containsKey(pnode.col)) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(pnode.node.val);
                    map.put(pnode.col, list);
                } else {
                    List<Integer> list = map.get(pnode.col);
                    list.add(pnode.node.val);
                }
                    
                if (pnode.node.left != null) {
                    queue.add(new PowerNode(pnode.col - 1, pnode.node.left));
                }
                if (pnode.node.right != null) {
                    queue.add(new PowerNode(pnode.col + 1, pnode.node.right));
                }
            }
            
            // the reason to use treemap is we can output it here in order.
            for (List<Integer> list : map.values()) {
                listSet.add(list);
            }
            
            return listSet;
        }
        
        public class PowerNode {
            int col;
            TreeNode node;
            public PowerNode(int col, TreeNode node) {
                this.col = col;
                this.node = node;
            }
        }
    }

Log in to reply
 

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