Binary Tree Vertical Order Traversal

Leave a comment

December 14, 2016 by oneOokay

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:

  1. 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]
    ]
    
  2. Given binary tree [3,9,8,4,0,1,7],
         3
        /\
       /  \
       9   8
      /\  /\
     /  \/  \
     4  01   7
    

    return its vertical order traversal as:

    [
      [4],
      [9],
      [3,0,1],
      [8],
      [7]
    ]
    
  3. Given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0’s right child is 2 and 1’s left child is 5),
         3
        /\
       /  \
       9   8
      /\  /\
     /  \/  \
     4  01   7
        /\
       /  \
       5   2
    

    return its vertical order traversal as:

    [
      [4],
      [9,5],
      [3,0,1],
      [8,2],
      [7]
    ]

一个二叉树的vertical order traversal.

  • 从左到右输出,所以输出是要有序的,且从小到大.
  • 总体应该是一个key-value pair的形式或者bucket/array的形式ArrayList[], 每个col(int)对应的应该是一个集合ArrayList用来放该col的所有的node
    • 如果是key-value Pair:
      • HashMap 需要进行for loop 按key增长输出:因为HashMap无序
      • TreeMap是自动按照key value排序的,所以可以按treemap.values()的顺序输出
    • 如果是bucket/Array的形式,那么需要先得到bucket和array的上下限,即最左的col数和最右的col数.
  • 计算节点的‘col’,在树的遍历里面怎么根据父亲计算儿子的col?(我试图用下标数来找找下层和上层之间的联系,方向就错了。)
    • 观察可得,左儿子的col=父亲col-1;右儿子的col=父亲col+1.所以可以从root开始,定一个值。

解法:

  1. HashMap或者TreeMap
    • BFS层遍历 Tree。在遍历的同时要记录当前node的col:
    • 可以新建一个class包含Node和当前的col
    • 或者用两个queue,一个queue放Node,一个queue放该Node处于第几个column。所以以后如果要存对应的两个值的话,保持其顺序,就用两个queue来实现。我好像记得以前做过一个类似的用两个queue来存东西的,但是找不到了=。=
    • Root算作col=0 (其实任何数都行),把root放入node queue里面,把col放到column里面。
    • 如果Node.left不为空,那么Node.left的col为Node的col – 1。如果这个值不存在TreeMap里,就先把它加上。同理Node.right的col为Node的col + 1。
    • HashMap: 同时维持一个colMax和colMin最终for-loop从TreeMap里面按照colMin到colMax取出ArrayList形成result
    • TreeMap:treemap.values()逐个加入到ans输出即可
  2. bucket/ArrayList:
    • Recursion求得min和max
public List<TreeNode> verticalOrder(TreeNode root) {
        List<TreeNode> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        Map<Integer, ArrayList> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<Integer> colq = new LinkedList<Integer>();
        q.offer(root);
        colq.offer(1);
        int colMin = 1;
        int colMax = 1;
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            int col = colq.poll();
            if (!map.containsKey(col)){
                map.put(col, new ArrayList<TreeNode>());
            }
            map.get(col).add(node.val);
            if (node.left != null){
                q.offer(node.left);
                colq.offer(col - 1);//这里不能够用col --,因为接下来的right的
col是要based on最初的col值的
                colMin = Math.min(colMin, col - 1);
            }
            
            if (node.right != null){
                q.offer(node.right);
                colq.offer(col + 1);
                colMax = Math.max(colMax, col + 1);
            }
        }
        //HashMap
        for (int i = colMin; i <= colMax; i ++){
            ans.add(map.get(i));
        }
        //TreeMap
        for (ArrayList<Integer> v : map.values()){
            ans.add(v);
        }
        return ans;        
    }
//range为int[2]
public void getRange(TreeNode root, int[] range, int col) {
    if (root == null) {
        return;
    }
    range[0] = Math.min(range[0], col);
    range[1] = Math.max(range[1], col);
    
    getRange(root.left, range, col - 1);
    getRange(root.right, range, col + 1);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: