写点什么

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

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

一、题目描述

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

 

例如:

给定二叉树: [3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

返回其层次遍历结果:

[

[3],

[20,9],

[15,7]

]

 

提示:

节点总数 <= 1000

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路

利用双端队列的两端皆可添加元素的特性,设打印列表(双端队列) tmp ,并规定:

  • 奇数层 则添加至 tmp 尾部 ,

  • 偶数层 则添加至 tmp 头部 。



算法流程:
  1. 特例处理: 当树的根节点为空,则直接返回空列表 [] ;

  2. 初始化: 打印结果空列表 res ,包含根节点的双端队列 deque ;

  3. BFS 循环: 循环打印奇 / 偶数层,当 deque 为空时跳出;

打印奇数层: 从左向右 打印,先左后右 加入下层节点;

若 deque 为空,说明向下无偶数层,则跳出;

打印偶数层: 从右向左 打印,先右后左 加入下层节点;

  1. 返回值: 返回打印结果列表 res 即可;

复杂度分析:
  • 时间复杂度 O(N)

  • 空间复杂度 O(N)

三、代码实现

class TreeNode{        int val;        TreeNode left;        TreeNode right;        TreeNode(int x){            this.val =x;        }    }    public List<List<Integer>> levelOrder(TreeNode root) {        Deque<TreeNode> deque = new LinkedList<>();        List<List<Integer>> res = new ArrayList<>();        if(root != null) deque.add(root);        while(!deque.isEmpty()) {            // 打印奇数层            List<Integer> tmp = new ArrayList<>();            for(int i = deque.size(); i > 0; i--) {                // 从左向右打印                TreeNode node = deque.removeFirst();                tmp.add(node.val);                // 先左后右加入下层节点                if(node.left != null) deque.addLast(node.left);                if(node.right != null) deque.addLast(node.right);            }            res.add(tmp);            if(deque.isEmpty()) break; // 若为空则提前跳出            // 打印偶数层            tmp = new ArrayList<>();            for(int i = deque.size(); i > 0; i--) {                // 从右向左打印                TreeNode node = deque.removeLast();                tmp.add(node.val);                // 先右后左加入下层节点                if(node.right != null) deque.addFirst(node.right);                if(node.left != null) deque.addFirst(node.left);            }            res.add(tmp);        }        return res;    }
复制代码


四、小结

这里的双端队列比较需要注意,因为开始我用的是指针标识+队列来判断正序打印还是倒序打印,遇到的问题就是跨节点的树没法保证是同一层级。

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

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

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

评论

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