层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //最终的返回结果，存储每一层的节点
        List<List<Integer>> res = new ArrayList<>();
        //如果根节点为空，则直接返回
        if(root==null) return res;
        //队列，按照先进先出的顺序将每一层的节点从左往右顺序弹出
        LinkedList<TreeNode> queue = new LinkedList<>();
        //根节点进队
        queue.add(root);
        while(!queue.isEmpty()){
            //存储某层所有节点的值
            List<Integer> list = new ArrayList<>();
            //记录当前层的节点大小
            int size = queue.size();
            //每次队列中弹出的节点
            TreeNode node;
            for(int i = 0; i < size; i++){
                node = queue.poll();
                //若子节点不为空，则加入到队列中
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                list.add(node.val);
            }
            //将该层加入到结果中
            res.add(list);
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //最终的返回结果，存储每一层的节点
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, 0, root);
        return res;
    }
    public void dfs(List<List<Integer>> res, int level, TreeNode root){
        //如果root为空，直接返回
        if(root==null) return;
        //若root节点所在的深度等于res的大小，则说明root节点所在的索引处还没有list，则添加一个list
        if(level==res.size()){
            res.add(new ArrayList<>());
        }
        //根据root节点的深度确定它在res中的索引并添加它的值
        res.get(level).add(root.val);
        //处理子节点
        dfs(res, level+1, root.left);
        dfs(res, level+1, root.right);
    }
}