Java 6ms simple solution, updating two numbers for leftmost and rightmost deviation


  • 0
    Y

    Simple logic and data structure. Note that I keep updating two integers representing the leftmost and rightmost deviations. I also used LinkedList for result for faster head insertion.

       public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if (root == null) {
                return result;
            }
            int leftMost = 0;
            int rightMost = 0;
            // maps tree node to its deviation
            Map<TreeNode, Integer> node2dev = new HashMap<TreeNode, Integer>();
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offerLast(root);
            node2dev.put(root, 0);
            result.add(new ArrayList<Integer>());
            while(queue.size() != 0) {
                TreeNode curr = queue.pollFirst();
                int dev = node2dev.get(curr);
                if (dev < leftMost) {
                    leftMost = dev;
                    result.add(0, new ArrayList<Integer>());
                } else if (dev > rightMost) {
                    rightMost = dev;
                    result.add(new ArrayList<Integer>());
                }
                result.get(dev - leftMost).add(curr.val);
                // enqueue left and right child
                if (curr.left != null) {
                    node2dev.put( curr.left, dev - 1 );
                    queue.offerLast(curr.left);
                }
                if (curr.right != null) {
                    node2dev.put( curr.right, dev + 1 );
                    queue.offerLast(curr.right);
                }
            }
            return result;
        }

Log in to reply
 

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