【LeetCode】二叉树的层序遍历 Java 题解

关注

发布于: 1 小时前

题目描述

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


示例：二叉树：[3,9,20,null,null,15,7],
    3   / \  9  20    /  \   15   7返回其层序遍历结果：
[  [3],  [9,20],  [15,7]]
作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

思路

这个题目是考察二叉树的层序遍历，一般采用广度优先思想解决。
广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。该算法从一个根节点开始，首先访问节点本身。然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
在 Java 中, 我们一般使用 Queue 这种数据结构实现广度优先遍历。

代码

/** * 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) {        List<List<Integer>> ans = new ArrayList<>();        if (root == null) {            return ans;        }        Queue<TreeNode> queue = new ArrayDeque<>();        queue.offer(root);        while (!queue.isEmpty()) {            List<Integer> temp = new ArrayList<>();            int size = queue.size();            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll();                temp.add(node.val);                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }            ans.add(temp);        }
        return ans;    }}

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 1 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/5c69c61df62236df17f43d38f】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】二叉树的层序遍历 Java 题解

题目描述

思路

代码

总结

HQ数字卡

评论