class Solution {
  	//定义全局结果
  	ArrayLIst<ArrayList<Integer>> res = new ArrayList();
  
    public ArrayLIst<ArrayList<Integer>> levelOrder (TreeNode root) {
      if(root==null) return res;
      //借助链表来完成层序遍历
      LinkedList<TreeNode> path = new LinkedList();
      level(root, path);
      return res;
    }
  
  	public void level (TreeNode root, LinkedList<TreeNode> path) {
      //先加入第一个节点
      path.addLast(root);
      //遍历链表
      while(!path.isEmpty()){
        //获取当前层的节点数
        int size = path.size();
        //定义存储每层的节点
        ArrayList<Integer> levelval = new ArrayList();
        //遍历当前层
        for(int i=0; i<size; i++){
          //获取遍历节点
          TreeNode tmp = path.pollLast();
          //将其加入到层list里面
          levelval.add(tmp.val);
          //加入左右子节点
          if(tmp.left!=null) path.addLast(tmp.left);
          if(tmp.right!=null) path.addLast(tmp.right);
        }
        //将每层的结果放入到全局结果中
        res.add(new ArrayList(levelval));
      }
    }
}

class Solution:
   def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if root is None:
          return []
        res = []
        path = [root]
        while(path):
            arr = []
            for _ in range(len(path)):
                obj = path.pop(0)
                arr.append(obj.val)
                if obj.left: 
                    path.append(obj.left)
                if obj.right: 
                    path.append(obj.right)
            res.append(arr)
        return res