【LeetCode】102.二叉树的层序遍历

1.问题

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

"图1"

示例 1

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

示例 2

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

示例 3

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

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

2.解题思路

2.1 队列

二叉树每层的遍历符合队列的特性，必须FIFO(first in first out)，再遍历每层完成后，可以给定一个标记或者层数，表示该层已经遍历完毕，可以将此时的该层遍历结果输出。伪代码：

//定义队列
Queue q;
//结果集
List res;
//root 入队
q.add(root);
//给定一个标识，标记第一层遍历的结尾
q.add(null);
while(q不为空){
	//出队
	temp=q.peek();
	//不是标识的话，入队root.left、root.right
	if(temp不为null){
		res.add(temp.val);
		if(temp.left不为null){
			q.add(temp.left);
		}
		if(temp.right不为null){
			q.add(temp.right);
		}
	}
	//否则，该层遍历完毕
	else {
		q.add(null);
	}
}

"图2"

复杂度分析：

• 时间复杂度：O(n)，其中n为二叉树的节点数，每个节点访问一次
• 空间复杂度：O(n)，队列的空间为二叉树的一层的节点数，最坏情况二叉树的一层为O(n)级

2.2 递归

根据二叉树的定义，不难看出，每个节点都有类似的性质。当遍历发生时，对于其左右子树同样适用相同的规则，非常适合递归。可以借鉴之前对于二叉树的前中后序遍历，既然可以用递归解决，那层次遍历也未尝不可。同样可以运用标记的思想，对于同一层，可以标记为相同的深度来进行遍历。伪代码：

void traverse(TreeNode root, int depth);

//计入子节点，则深度depth+1
//递归左右时深度记得加1
traverse(root.left, depth + 1); 
traverse(root.right, depth + 1);

//每个节点值放入对应的二维数组相应行
res[depth - 1].push_back(root->val);

复杂度分析

• 时间复杂度：O(n)，n为节点数量，DFS对每个节点访问一次，因此递归调用n次，每次调用执行常数次操作，时间复杂度O(n)。
• 空间复杂度：O(n)，空间复杂度在于递归调用深度和每次递归调用辅助空间，辅助空间为常数级，与节点深度相关，当节点深度为n时最大，为O(n)。

3.代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 利用队列的性质
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (null == root) {
            return new ArrayList<>();
        }
        //结果
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //每层临时结果
        ArrayList<Integer> temp = new ArrayList<>();
        TreeNode node;
        //队列
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(root);
        //给定个 层标识
        list.add(null);
        //遍历队列
        while (!list.isEmpty()) {
            node = list.removeFirst();
            if (null != node) {
                temp.add(node.val);
                if (null != node.left) {
                    list.add(node.left);
                }
                if (null != node.right) {
                    list.add(node.right);
                }
            }
            //为null节点，说明这一层已经遍历完成
            else {
                //这里一定要判断下，如果为空，表明二叉树已经遍历完成了
                if (!temp.isEmpty()) {
                    res.add(temp);
                    temp = new ArrayList<>();
                    list.add(null);
                }

            }
        }
        return res;
    }
	
	//记录输出
    ArrayList<ArrayList<Integer> > res = new ArrayList();
    
	//递归
	public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if(root == null)
            //如果是空，则直接返回
            return res;
        //递归层次遍历
        traverse(root, 0);
        return res;
    }
    
    //临时结果集
    ArrayList<Integer> row;
    
	void traverse(TreeNode root, int depth) {
        if(root != null){
            //新的一层: 对于二维res来说，将根视为第0层，树的深度正好等于一维res的个数
            if(res.size() == depth){ 
                row = new ArrayList();
                res.add(row);
            //读取该层的一维数组，将元素加入末尾
            }else{
                row = res.get(depth); 
            }
            row.add(root.val);
        }
        else
            return;
        //递归左右时深度记得加1
        traverse(root.left, depth + 1);
        traverse(root.right, depth + 1);
    }
}