[数据结构与算法]102. 二叉树的层序遍历

1、题目描述

2、题目分析 【该题是非常经典的题目！】

可参考之前分析文章：二叉树的层序遍历(从上到下，从下到上，之字/锯齿/蛇形)

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。

最基本的是树的结构体（根，左子树，右子树）

//树的结构体
class TreeNode{
    int val;
    TreeNode left; 
    TreeNode right;
    TreeNode(int val){
       this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right){
       this.val = val;
       this.left = left;
       this.right = right;
    }
}

【层序遍历】方法一：

DFS-递归解题思路

代码分析：

1、如果深度为res的长度，则开启新的一层用于记录（这一行比较难理解）

 //此时深度为res的长度，开启新的ArrayList<Integer>用于记录这一层
 if(depth == res.size()){
    res.add(new ArrayList<Integer>());
 }

2、在当前list行进行元素追加

res.get(depth).add(node.val);

?3、完整代码如下：

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root,0);
        return res;
    }

    private void dfs(TreeNode node ,int depth){
       if(node == null) return;
       //此时深度为res的长度，开启新的ArrayList<Integer>用于记录这一层
       if(depth == res.size()){
          res.add(new ArrayList<Integer>());
       }
       
       res.get(depth).add(node.val);
       if(node.left != null) dfs(node.left, depth+1);   
       if(node.right != null) dfs(node.right, depth+1);         
    }
}

复杂度分析

时间复杂度：O(N),??N代表树节点的个数，树每个节点都会遍历到。
空间复杂度：O(h)，h 是树的高度

【层序遍历】方法二：

BFS-广度优先解题思路（这道题是非常经典的题目，必须两个方法都掌握）

使用容器进行迭代遍历，BFS使用的是【队列】。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> res = new ArrayList<List<Integer>>();
       if(root == null) return res;
       //使用容器进行遍历，BFS使用的是【队列】
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.offer(root);
       while(!queue.isEmpty()){
          List<Integer> line = new ArrayList<Integer>();
          int lineCount = queue.size();
          while(lineCount > 0){
             TreeNode node = queue.poll();
             line.add(node.val);
             lineCount--;
             //判定TreeNode的左右子树是否为null, 不为空也压入队列 
             if(node.left != null)
                 queue.offer(node.left);
             if(node.right != null)
                 queue.offer(node.right);
          }
          res.add(line);
       }
       return res;
    }
}

复杂度分析

记树上所有节点的个数为 n。

时间复杂度：O(n)，每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：O(n)，队列中元素的个数不超过 n?个，故渐进空间复杂度为 O(n)。