Title Link: https://www.nowcoder.com/study/live/716/5/17

Given a binary tree, return the sequence traversal result of the binary tree (traversing layer by layer from left to right)
For example:
The given binary tree is {3,9,20, #, #, 15,7},

The result of the binary tree sequence traversal is
[
[3],
[9,20],
[15,7]

]

Tips:
0 < = node number of binary tree < = 1500

Example 1
input
{1,2}
output
[[1],[2]]
Example 2
input
{1,2,3,4,#,#,5}
output
[[1],[2,3],[4,5]]

Problem solution

1. Due to the requirements of the topic, in the output results, each layer corresponds to an ArrayList. Therefore, it is necessary to make a little change to the traditional level traversal algorithm and reflect the number of layers during traversal.
2. We need to record the number of layers of each node, so we use two queues. One queue stores the parent node, and the other queue stores the corresponding number of layers.
3. Only recording the number of layers of each node cannot achieve the output required by the topic. We need to record the output of each layer, and then add it to the total ArrayList after the end of each layer. The difficulty here is how to judge the end of the first floor.
4. How to judge the end of a layer (method 1): I use a variable to record the number of layers currently traversed. During normal traversal, the number of layers satisfying the parent + 1 = = the number of layers currently traversed. Once this condition is not satisfied, it means that the number of parent layers changes, that is, the number of layers currently traversed needs to change. Therefore, the "current traversal layers" is updated to parent layers + 1 at this time. Thus, the number of perceived layers changes.
5. How to judge the end of a layer (method 2): record the number of layers of two adjacent parent nodes. If they are inconsistent, the number of layers will change.
6. How to judge the end of a layer (method 3): for each while loop, let a whole layer of parent nodes out of the queue, rather than just one parent node out of the queue. Thus, while corresponds to one layer at a time, and there is no need to record the current number of layers.

realization

Method 1 Code:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode class
     * @return int Integer ArrayList < ArrayList < > >
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> curLevelRes = new ArrayList<>();
        int curLevel = 1;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> layerQueue = new LinkedList<>();

        curLevelRes.add(root.val);
        nodeQueue.add(root);
        layerQueue.add(curLevel);

        while (!nodeQueue.isEmpty()) {
            TreeNode parent = nodeQueue.poll();
            Integer parentLayer = layerQueue.poll();

            if (parentLayer + 1 != curLevel) { // curLevel change
                curLevel = parentLayer + 1;
                res.add(curLevelRes);
                curLevelRes = new ArrayList<>();
            }
            
            TreeNode left = parent.left;
            TreeNode right = parent.right;
            if (left != null) {
                curLevelRes.add(left.val);
                nodeQueue.add(left);
                layerQueue.add(curLevel);
            }
            if (right != null) {
                curLevelRes.add(right.val);
                nodeQueue.add(right);
                layerQueue.add(curLevel);
            }
        }

        return res;
    }
}

Method 2 Code:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     *
     * @param root TreeNode class
     * @return int Integer ArrayList < ArrayList < > >
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> curLevelRes = new ArrayList<>();
        int lastParentLayer = 0;
        int curParentLayer = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> layerQueue = new LinkedList<>();

        curLevelRes.add(root.val);
        nodeQueue.add(root);
        layerQueue.add(curParentLayer + 1);

        while (!nodeQueue.isEmpty()) {
            TreeNode parent = nodeQueue.poll();
            Integer parentLayer = layerQueue.poll();

            lastParentLayer = curParentLayer;
            curParentLayer = parentLayer;
            if (lastParentLayer != curParentLayer) { // curLevel change
                res.add(curLevelRes);
                curLevelRes = new ArrayList<>();
            }

            TreeNode left = parent.left;
            TreeNode right = parent.right;
            if (left != null) {
                curLevelRes.add(left.val);
                nodeQueue.add(left);
                layerQueue.add(curParentLayer + 1);
            }
            if (right != null) {
                curLevelRes.add(right.val);
                nodeQueue.add(right);
                layerQueue.add(curParentLayer + 1);
            }
        }
        return res;
    }
}

Method 3 code:

public class Solution {
    /**
     *
     * @param root TreeNode class
     * @return int Integer ArrayList < ArrayList < > >
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Queue<TreeNode> parentQueue = new LinkedList<>();
        res.add(new ArrayList<>(Arrays.asList(root.val)));
        parentQueue.add(root);

        while (!parentQueue.isEmpty()) {
            ArrayList<Integer> curLevelList = new ArrayList<>();
            int size = parentQueue.size();
            // Take care: parentQueue.size() is not effectively final!
            for (int i = 0; i < size; i++) {

                TreeNode parent = parentQueue.poll();
                TreeNode left = parent.left;
                TreeNode right = parent.right;
                if (left != null) {
                    curLevelList.add(left.val);
                    parentQueue.add(left);
                }
                if (right != null) {
                    curLevelList.add(right.val);
                    parentQueue.add(right);
                }
            }

            // When traversing the last layer, it's empty.
            if (!curLevelList.isEmpty()) {
                res.add(curLevelList);
            }
        }
        return res;
    }
}