写点什么

算法攻关 - 从上到下打印二叉树 (O(n))_offer32

发布于: 2021 年 03 月 10 日
算法攻关-从上到下打印二叉树(O(n))_offer32

一、题目描述

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


 


例如:

给定二叉树: [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 通常借助 队列 的先入先出特性来实现。

处理流程:

我们记得当时求二叉树的最大深度的时候我们用了 2 种办法,一种是 DFS,一种是 BFS。而 BFS 则就是利用队列将每一层节点都存放起来并遍历结果。

三、代码实现

class TreeNode{        int val;        TreeNode left;        TreeNode right;        TreeNode(int x){            this.val=x;        }    }    public int[] levelOrder(TreeNode root) {        //边界条件-如果根节点为null退出        if(root == null) return new int[0];        //利用初始化队列的方式将根节点填充进入队列        Queue<TreeNode> queue = new LinkedList<>(){{ offer(root); }};        //额外数组来存储最终结果        ArrayList<Integer> ans = new ArrayList<>();        //当队列不为空        while(!queue.isEmpty()) {            //从队列获取节点            TreeNode node = queue.poll();            //并维护结果保存            ans.add(node.val);            //如果左节点不为空,则添加到队列            if(node.left != null) queue.offer(node.left);            //如果右节点不为空,则添加到队列            if(node.right != null) queue.offer(node.right);        }        //遍历结果将值换到数组        int[] res = new int[ans.size()];        for(int i = 0; i < ans.size(); i++)            res[i] = ans.get(i);        return res;    }
复制代码

四、小结

这里面的思路其实就是套用 BFS 的模版即可。


发布于: 2021 年 03 月 10 日阅读数: 7
用户头像

小胜靠智,大胜靠德 2019.06.27 加入

历经创业、京东、腾讯、滴滴公司,希望能够有些东西一起分享。公众号:小诚信驿站,微信/CSDN搜索:wolf_love666

评论

发布
暂无评论
算法攻关-从上到下打印二叉树(O(n))_offer32