102.二叉树的层序遍历

题目

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

 

示例：
二叉树：[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

方法（广度优先搜索）

用一个队列结构来实现广度优先搜索。从根节点开始搜索，每次遍历同一层的全部节点，使用一个列表存储该层的节点值。

• 时间复杂度：O(n) 需要遍历到树中的每一个节点
• 空间复杂度：O(n) 队列的长度不超过n

代码

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

方法（深度优先搜索）

在每次第一次遍历到一层时，在结果数组res中添加一个新的空数组。在之后的遍历过程中，将节点值加入到该层在res中对应的数组中。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return res;
        dfs(root, 1);
        return res;
    }
    public void dfs(TreeNode root, int level){
        if(root == null)
            return;
        if(level == res.size() + 1)
            res.add(new ArrayList<>());
        res.get(level - 1).add(root.val);
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}