二叉树的层序遍历 3

题目地址(102. 二叉树的层序遍历)

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

/**
 * 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 {
        public List<List<Integer>> levelOrder(TreeNode root) {
            ArrayList<List<Integer>> res = new ArrayList<>();
            //使用队列来存储层序遍历的节点
            Queue<TreeNode> queue = new LinkedList<>();
            if(root==null){
                return res;
            }
            queue.offer(root);
            while (!queue.isEmpty()) {
                ArrayList<Integer> temp = new ArrayList<>();
                //每次循环的时候size都不一样大小 1 -> 2 -> 4 大概这样的
                int len = queue.size();
                //循环当前层的节点数量
                while (len > 0) {
                    //弹出最先进去的节点 并放到队列中
                    TreeNode poll = queue.poll();
                    temp.add(poll.val);
                    //将节点的左右节点放入队列(如果有)
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    }
                    len--;
                }
                res.add(temp);
            }
            return res;
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=G44FD)
• 空间复杂度：#card=math&code=O%28n%29&id=TP7xr)