Leetcode sword finger offer 32 - ii Print binary tree II from top to bottom

Title Description ：

Print binary tree from top to bottom , Nodes of the same layer are printed from left to right , Print each layer to a line .

for example :
Given binary tree : [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Return its hierarchical traversal result ：

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

Tips ：

1. Total number of nodes <= 1000

Their thinking ：

I. Print by layer ： The title requires the of binary tree Top to bottom Print （ Print by layer ）, Also known as binary tree Breadth first search （BFS）.BFS Usually with queue The first in first out feature of .

II. Print to one line per layer ： Print all nodes of this layer to one line , And add all nodes of the next layer to the queue , And so on , It can be printed in multiple lines .

Algorithm flow ：

    Special case handling ： When the root node is empty , Then return to the empty list [] ;
    initialization ： Print result list res = [] , The queue containing the root node queue = [root] ;
    BFS loop ： When the queue queue Jump out when empty ;
        Create a new temporary list tmp , Used to store the print results of the current layer ;
        Current layer print cycle ： The number of cycles is the number of nodes in the current layer （ That's the queue queue length ）;
            Out of the team ： The first element out of the team , Write it down as node;
            Print ： take node.val Added to the tmp The tail ;
            Add child nodes ： if node Left of （ Right ） The child node is not empty , Turn left （ Right ） Child nodes join the queue queue ;
        Results the current layer tmp Add in res .
    Return value ： Return to the list of print results res that will do .

Java Program ：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}