import java.util.*;

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


public class Solution {
    /**
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write code here

        // write code here
        LinkedList<TreeNode> queueFather = new LinkedList<>();
        LinkedList<TreeNode> queueChild = new LinkedList<>();

        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        if (root != null) {
            queueFather.add(root);
        }

        while (queueFather.size() > 0 || queueChild.size() > 0) {
            ArrayList<Integer> rowList = new ArrayList<>();
            if (queueFather.size() > 0) {
                while (queueFather.size() > 0) {
                    TreeNode node = queueFather.pop();
                    if (node.left != null) {
                        queueChild.add(node.left);
                    }
                    if (node.right != null) {
                        queueChild.add(node.right);
                    }
                    rowList.add(node.val);
                }
            } else{
                while (queueChild.size() > 0) {
                    TreeNode node = queueChild.pop();
                    if (node.left != null) {
                        queueFather.add(node.left);
                    }
                    if (node.right != null) {
                        queueFather.add(node.right);
                    }
                    rowList.add(node.val);
                }

            }
            resultList.add(rowList);

        }
        return resultList;
    }
}