6ms, BFS solution.


  • 0
    R

    Basically, the idea is: traverse all nodes using bfs, keep track of all nodes vertical order using map, which is, left node is 1 less than root and right node is 1 more than root.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            } else {
                Queue<Item> queue = new LinkedList<>();
                queue.offer(new Item(root, 0));
                Item dummy = new Item(null, Integer.MAX_VALUE);
                queue.offer(dummy);
                int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
                while (!queue.isEmpty()) {
                    Item it = queue.poll();
                    if (queue.isEmpty() && it == dummy) {
                        break;
                    } else if (it == dummy) {
                        queue.offer(dummy);
                    } else {
                        int order = it.order;
                        min = Math.min(min, order);
                        max = Math.max(max, order);
                        if (!map.containsKey(order)) {
                            map.put(order, new ArrayList<>());
                        }
                        map.get(order).add(it.node.val);
                        if (it.node.left != null) {
                            queue.offer(new Item(it.node.left, it.order - 1));
                        }
                        if (it.node.right != null) {
                            queue.offer(new Item(it.node.right, it.order + 1));
                        }
                    }
                }
                for (int i = min;i <= max; i++) {
                    result.add(map.get(i));
                }
                return result;
            }
        }
        
        class Item {
            TreeNode node;
            int order;
            public Item(TreeNode n, int o) {
                this.node = n;
                this.order = o;
            }
        }
    }
    

Log in to reply
 

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