314. Binary Tree Vertical Order Traversal

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7

Output:

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

Examples 3:

Input: [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

Output:

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

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Code

655. Print Binary Tree

class Solution {
    int min = 0;
    int max = 0;

    // 找到树的最左边和最右边
    private void helper(TreeNode root, int index){
        if(root == null) return;
        min = Math.min(min, index);
        max = Math.max(max, index);
        helper(root.left, index - 1);
        helper(root.right, index + 1);
    }

    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res =  new ArrayList<>();
        if (root == null) return res;
        helper(root, 0);

        for(int i = min; i <= max; i++){
            res.add(new ArrayList<>());
        }

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> index = new LinkedList<>();

        queue.offer(root);
        index.offer(-min);

        while(!queue.isEmpty()){
            TreeNode curr = queue.poll();
            int currIndex = index.poll();
            res.get(currIndex).add(curr.val);
            if (curr.left != null) {
                queue.offer(curr.left);
                index.offer(currIndex - 1);
            }

            if (curr.right != null) {
                queue.offer(curr.right);
                index.offer(currIndex + 1);
            }
        }
        return res;
    }
}