102. 二叉树的层序遍历

一、题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

二、解题

BFS

使用广度优先遍历，然后使用队列保存每一层的数据。BFS比较好想。

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> per = new ArrayList<>();
        if(root == null){
    
            return res;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
    
            int size = queue.size();
            for(int i = 0;i<size;i++){
    
                TreeNode node = queue.poll();
                per.add(node.val);
                if(node.left != null){
    
                    queue.add(node.left);
                }
                if(node.right != null){
    
                    queue.add(node.right);
                }
            }
            res.add(new ArrayList<>(per));
            per = new ArrayList<>();
        }
        return res;
    }
}

DFS

深度优先遍历，使用深度，每一层都创建一个新的集合，然后根据树的层数添加每一层的数据。

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
       //DFS
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
    
            return res;
        }
        dfs(root,0,res);
        return res;
    }
    public void dfs(TreeNode root,int depth,List<List<Integer>> res){
    
        //跳出条件
        if(root == null){
    
            return;
        }
        //每一层都加入一个新的集合
        if(depth == res.size()){
    
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        dfs(root.left,depth+1,res);
        dfs(root.right,depth+1,res);      
    }
}