Yyds dry inventory solution sword finger offer: print the binary tree into multiple lines

1. sketch ：

describe

Given the number of nodes is n Binary tree , It is required to print the binary tree layer by layer from top to bottom val value , The nodes of the same layer output from left to right , Output one line per layer , Store the output results in a two-dimensional array and return . for example ：

The given binary tree is {1,2,3,#,#,4,5}

The result of traversal of the binary tree is [[1],[2,3],[4,5]]

Data range ： The number of nodes in a binary tree  , requirement ： Spatial complexity  , Time complexity  

Input description ：

Given the root node of a binary tree

Example 1

Input ：

Log in and copy

      
      

       
       {1,2,3,#,#,4,5}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       [[1],[2,3],[4,5]]
      
      
      
      

       
       
1.
      
      

Example 2

Input ：

Log in and copy

      
      

       
       {8,6,10,5,7,9,11}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       [[8],[6,10],[5,7,9,11]]
      
      
      
      

       
       
1.
      
      

Example 3

Input ：

Log in and copy

      
      

       
       {1,2,3,4,5}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       [[1],[2,3],[4,5]]
      
      
      
      

       
       
1.
      
      

Example 4

Input ：

Log in and copy

      
      

       
       {}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       []
      
      
      
      

       
       
1.
      
      

2. Code implementation ：

Log in and copy

      
      

       
       import java.util.*;
       
       
public class Solution {
       
       
    // Level traversal 
       
       
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
       
       
        TreeNode head = pRoot;
       
       
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
       
       
        if(head == null)
       
       
            // If it's empty , It returns an empty array directly 
       
       
            return res; 
       
       
        // Queue storage , Perform hierarchical traversal 
       
       
        Queue<TreeNode> temp = new LinkedList<TreeNode>(); 
       
       
        temp.offer(head);
       
       
        TreeNode p;
       
       
        while(!temp.isEmpty()){
       
       
            // Record a row of a binary tree 
       
       
            ArrayList<Integer> row = new ArrayList<Integer>();
       
       
            int n = temp.size();
       
       
            // Because the first entry is the root node , Therefore, the number of nodes in each layer , The size of the queue is 
       
       
            for(int i = 0; i < n; i++){
       
       
                p = temp.poll();
       
       
                row.add(p.val);
       
       
                // If left and right children exist , Then save the left and right children as the next level 
       
       
                if(p.left != null)
       
       
                    temp.offer(p.left);
       
       
                if(p.right != null)
       
       
                    temp.offer(p.right);
       
       
            }
       
       
            res.add(row);
       
       
        }
       
       
        return res;
       
       
    }
       
       
    
       
       
}
       
       

      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.