Leetcode 102.二叉树层序遍历

力扣传送门(opens new window)

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：

常规思维法

我们理一遍题意：给定一棵二叉树，把这棵二叉树一层一层地访问一遍，并且存储在一个二维数组里面。

这里面的难点就是怎么做到每次取一层的元素。

我们考虑使用队列来存储每一层的元素。为什么使用队列呢？因为对同一层的节点，先访问，再把他们存储到一个数组里，存储的顺序要和访问的顺序一致，而队列的特点就是先进先出，和我们的要求一致，所以考虑使用队列来实现本题。

算法如下：

1. 首先，我们创建一个队列，用来访问节点（不一定是同一层）；创建一个列表，用来存储同一层的节点；创建一个二维列表，用来存储最终的答案。
2. 然后，先对根节点做处理，把根节点加入队列，用列表存储，在二维列表里面加入刚才的列表，这样，第一层节点就存储好了。
3. 到了第二层，我们再创建一个列表，用来存储第二层的节点，并获取一下队列的长度，这里队列的长度是多少，接下来就要进行几次循环，每次循环是访问并存储当前节点的左子节点和右子节点。
4. 每次循环要做的工作是：弹出队列头部的一个节点，将这个节点的左子节点和右子节点加入队列，并且把左子节点和右子节点的值存进刚才的列表。
5. 若干次循环完成后，队列里面就都是下一层的节点，列表已经存好了这一层的节点。
6. 把列表加入二维列表。
7. 重复第3~6步，直到队列为空。

代码实现：

class Solution {
    List<List<Integer>> res = new ArrayList(); 

    public List<List<Integer>> levelOrder(TreeNode root) {
        // 根节点为空，直接返回空结果列表
        if (root == null) {
            return res; 
        }
        // 创建一个队列用于层序遍历
        Queue<TreeNode> queue = new LinkedList(); 
        // 将根节点入队
        queue.add(root);

        while (!queue.isEmpty()) {
            // 当前层的节点数
            int size = queue.size(); 
            // 存储当前层节点值的列表
            List<Integer> list = new ArrayList(); 

            while (size-- > 0) {
                // 弹出队首节点
                TreeNode currNode = queue.poll();
                // 将节点值加入列表
                list.add(currNode.val); 

                if (currNode.left != null) {
                    // 将左子节点入队
                    queue.add(currNode.left); 
                }
                if (currNode.right != null) {
                    // 将右子节点入队
                    queue.add(currNode.right); 
                }
            }
            // 将当前层的节点值列表加入最终结果列表
            res.add(list); 
        }
        // 返回最终结果列表
        return res; 
    }
}

方法二：

递归实现

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList(); // 存储最终结果的列表
  
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            // 如果根节点为空，直接返回结果列表
            return res; 
        }
         // 从根节点开始进行深度优先搜索
        dfs(root, 0);
        // 返回最终结果
        return res; 
    }

    public void dfs(TreeNode root, int level) {
        if(root == null){
            // 如果当前节点为空，直接返回
            return; 
        }

        if (level == res.size()) {
            // 如果当前层级还未添加到结果列表中，先添加一个空列表
            res.add(new ArrayList<>()); 
        }
        // 将当前节点的值添加到对应层级的列表中
        res.get(level).add(root.val); 
        // 递归处理左子节点，层级加1
        dfs(root.left, level + 1); 
        // 递归处理右子节点，层级加1
        dfs(root.right, level + 1); 
    }
}