A, the title

Second, breadth first BFS

I’ll just write it out using the BFS template. See the previous blog for detailed analysis of the template.

The only catch is learning basic grammar and data structures as you brush through questions. I was a little confused at first about how to add elements to the list of two. You just have to create a new list and add to the list.

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> q =new LinkedList<>();
        q.offer(root);
        
        while(! q.isEmpty()){ int size = q.size(); List<Integer> A = new ArrayList<>();for(int i=0 ; i<size; i++){ root=q.poll(); A.add(root.val);if(root.left ! = null){ q.add(root.left); }if(root.right ! = null){ q.add(root.right); } / /else{returnnull; } } res.add(A); }returnres; }}Copy the code

Analysis of several bug points

1, A is defined outside of the function, and A complete for loop puts out A layer of data, so it can be defined outside.Return null (); It’s over after return. Null is a recursive way of writing because we’re used to boundary conditions because we’re adding elements to que, so we don’t return and we don’t do boundary checks

Third, the recursion

Train of thought

Return the root node, the left and right subtrees, and the left and right nodes of the left and right trees

code

I have recursion points, but how do I put them in a two-dimensional array? Think about it. But the two-dimensional array is really not familiar, did not want to come out, see the comments section of a big guy recursion idea after their own recurrence:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        // List<List<Integer>> res = new ArrayList<>();
        int lever = 0;
        levelOrder(root,lever);
        return res;
    }
    public void levelOrder(TreeNode root,int lever){
        if (root==null){
            return; } // ArrayList<Integer> list = new ArrayList<>(); // This is the first time for this layer to be expanded to store the elements of this layerif(res.size()==lever){ // list.add(); res.add(new ArrayList<Integer>()); } // The lever value of each layer in the recursion is the same as that of the next layer. // lever+1; lever = lever+1; levelOrder(root.left,lever); levelOrder(root.right,lever); }}Copy the code

Bug analysis encountered

At the beginning, after reading the big guy’s thinking, I rewrote it like this:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        // List<List<Integer>> res = new ArrayList<>();
        int lever = 0;
        levelOrder(root,lever);
        return res;

    }
    public void levelOrder(TreeNode root,int lever){
        if (root==null){
            return ;
        }
        ArrayList<Integer> list = new ArrayList<>(); 
        if(res.size()==lever){ list.add(root.val); } res.add(list); lever = lever+1; levelOrder(root.left,lever); levelOrder(root.right,lever); }}Copy the code

I began to wonder why, and sorted it out:For the above reason, the lever was the same for the same layer, but I expanded it every time, so naturally I couldn’t add it later, so I began to think about how to expand the lever only when the layer appeared for the first time. Refer to the comments found a trick:

if(res.size()==lever){
            // list.add();
            res.add(new ArrayList<Integer>());
        }
res.get(lever).add(root.val);

Copy the code

It’s great. Deal with it! Get (lever).add(node.val); You can use this function to add elements to a layer, instead of increasing the list in res each time so that the nodes of the same layer have the same lever as that one.

At first I thought about putting recursive parameters in the left and right subtrees, but it turned out that this was not only a logical hassle but it was very difficult for me to give up

 public void levelOrder(TreeNode root_left,TreeNode root_right,int lever){
        if (root_left==null&&root_right==null){
            return ;
        }
        ArrayList<Integer> list = new ArrayList<>(); 
        if(res.size()==lever){ list.add(root_left.val,root_right.val); } res.add(list); lever = lever+1; levelOrder(root_left.left,root_left.right,lever); levelOrder(root_right.left,root_right.right,lever); }}Copy the code