Friday, January 8, 2016

Leetcode: Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its vertical order traversal as:
[
  [9],
  [3,15],
  [20],
  [7]
]
Given binary tree [3,9,20,4,5,2,7],
    _3_
   /   \
  9    20
 / \   / \
4   5 2   7
return its vertical order traversal as:
[
  [4],
  [9],
  [3,5,2],
  [20],
  [7]
]



Understand the problem:

The problem can be solved like this:
1. First find out the vertical order of the leftmost node and rightmost node. 
2. Create a bucket with the size of righrmost order - leftmost order + 1. Each bucket should contain at least one node if the tree is a full tree. 
3. Then do a level-order traversal of the binary tree to determine the vertical order of each node, assign each node to the corresponding bucket. Since the tree traversal is from left to right, top to bottom, we can guarantee the requirement of the problem. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int leftMostOrder = Integer.MAX_VALUE;
    private int rightMostOrder = Integer.MIN_VALUE;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        // Step 1: find the leftmost and rightmost (NON-NECESSARY LEAF) node
        TreeNode p = root;
        findLeftRightMostOrder(p, 0);

        // Step 2: determine at most number of vertical orders
        int n = rightMostOrder - leftMostOrder + 1;
        List[] buckets = new List[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // Step 3: determine the vertical order for each tree node
        verticalOrderHelper(root, buckets, -leftMostOrder);
        
        // Step 4: form the result
        for (List bucket : buckets) {
            if (bucket.size() > 0) {
                result.add(bucket);
            }
        }
        
        return result;
    }
    
    private void verticalOrderHelper(TreeNode root, List[] buckets, int order) {
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> orderQueue = new LinkedList<>();
        nodeQueue.offer(root);
        orderQueue.offer(order);
        
        while (!nodeQueue.isEmpty()) {
            TreeNode currNode = nodeQueue.poll();
            int currOrder = orderQueue.poll();
            
            buckets[currOrder].add(currNode.val);
            
            if (currNode.left != null) {
                nodeQueue.offer(currNode.left);
                orderQueue.offer(currOrder - 1);
            }
            
            if (currNode.right != null) {
                nodeQueue.offer(currNode.right);
                orderQueue.offer(currOrder + 1);
            }
        }
    }
    
    // Find out the leftMost order
    private void findLeftRightMostOrder(TreeNode root, int order) {
        if (root == null) {
            return;
        }
        
        leftMostOrder = Math.min(leftMostOrder, order);
        rightMostOrder = Math.max(rightMostOrder, order);
        
        findLeftRightMostOrder(root.left, order - 1);
        findLeftRightMostOrder(root.right, order + 1);
    }
}

Summary:
There are a couple of error-prone points for this question.
 1. In the first step to find out the vertical order of the leftMost and rightMost node, we consider each node instead of only the leaf node.

 2. To determine the order of each node and save the result, we need to do a level-order traversal instead of a pre-order traveral. That's because the question asks for the print order from left to right, from top to bottom. If do a pre-order traversal, e.g.

    5
   / \
 1   6
  \
   3
  /  \
 2   4

If do a pre-order traversal, the print out order is 5 1 3 2 4 6, so node 4 will be print before node 6 (note that 4 and 6 has the same vertical order)

No comments:

Post a Comment