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

关注

发布于: 2021 年 03 月 13 日

一、题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [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-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思考

参考从上到下打印二叉树题目一，从上到下打印二叉树题目三

我们在第一个代码分层打印二叉树的所有节点的时候，用的 BFS 广度优先搜索，中间为了存储每层需要打印的变量，使用了队列来作为中间存储。那么这个题是上一个题的延伸，我们可以观察到他的改变点为每一层为一个数组打印。这个我们能想到的是，当时我们是遍历当前层的时候，将下一层的节点已经存放到队列中。

三、代码实现

class TreeNode{        int val;        TreeNode left;        TreeNode right;        TreeNode(int x){            this.val=x;        }    }    public List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> returnVal = new ArrayList<>();        //第一步边界条件的确认        if (root == null){            return returnVal;        }        //第二步我们基于之前第一版了解BFS模板执行层序遍历        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        //第三步遍历队列        while (!queue.isEmpty()){            List<Integer> levelVal = new ArrayList<>();            //第四步本题调整的内容-》将当前已经第一次确认的队列长度进行遍历，而节点内容进行队列保存，方便下一次遍历层级            for(int i= queue.size();i>0;i--){                TreeNode node = queue.poll();                if (node.left != null) queue.offer(node.left);                if (node.right != null) queue.offer(node.right);                levelVal.add(node.val);            }            returnVal.add(levelVal);        }        return returnVal;    }

复制代码

四、小结

BFS 的广度优先搜索遍历的时候，是否能调整优化下呢？ArrayList 可以指定下初始化大小。而初始化大小可以根据扩容机制进行调整。

发布于: 2021 年 03 月 13 日阅读数: 16

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

小诚信驿站

关注

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

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

发布

暂无评论

创作场景