写点什么

【LeetCode】从上到下打印二叉树 Java 题解

用户头像
HQ数字卡
关注
发布于: 1 小时前

题目描述

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。



例如:给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回:
[3,9,20,15,7]

提示:
节点总数 <= 1000
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 这个题目题意简洁明了,借助树这种数据结构,考察树和队列的相关知识。

  • 根据题意,我采用了 BFS 的方法解决这个问题。对于没有使用过 BFS 的同学,简要介绍一下 BFS 算法。

  • BFS 全称是 Breadth First Search,中文名是宽度优先搜索,也叫广度优先搜索。所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。

  • BFS 算法找到的路径是从起点开始的 最短 合法路径。这个很重要,在各位同学看到找最短路径的题目时候,脑海里可以考虑一下 BFS 算法。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int[] levelOrder(TreeNode root) {        List<Integer> nodeValList = new ArrayList<>();        bfs(root, nodeValList);        int size = nodeValList.size();        int[] ans = new int[size];        for (int i = 0; i < size; i++) {            ans[i] = nodeValList.get(i);        }        return ans;    }
public void bfs(TreeNode root, List<Integer> ans) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); ans.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } }}
复制代码


  • 上述代码,使用队列的时候,要注意队列的大小。每次都出队了一个元素,queue.size() 是动态获取队列的大小,为了保障我们把当前层的所有元素都取出,需要定义 size 变量,确定当前层的大小,获取当前层的所有元素。

总结

  • BFS 解法的时间复杂度是 O(n), 空间复杂度是 O(n)

  • 坚持每日一题,加油!

发布于: 1 小时前阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】从上到下打印二叉树Java题解