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

关注

发布于: 2021 年 03 月 12 日

一、题目描述

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

例如:
给定二叉树: [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 头部。

算法流程：

特例处理： 当树的根节点为空，则直接返回空列表 [] ；
初始化： 打印结果空列表 res ，包含根节点的双端队列 deque ；
BFS 循环：循环打印奇 / 偶数层，当 deque 为空时跳出；

打印奇数层：从左向右打印，先左后右加入下层节点；

若 deque 为空，说明向下无偶数层，则跳出；

打印偶数层：从右向左打印，先右后左加入下层节点；

返回值： 返回打印结果列表 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

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

小诚信驿站

关注

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

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

发布

暂无评论

创作场景