写点什么

手撸二叉树之二叉树的锯齿形层序遍历

发布于: 4 小时前
手撸二叉树之二叉树的锯齿形层序遍历

Hello, 大家好,今天是我参加 9 月更文的第 14 天,今天给大家带来的关于二叉树相关的算法题是从中序与后序遍历序列构造二叉树,正文如下:

题目

给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。


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


 3   / \  9  20    /  \   15   7
复制代码


返回锯齿形层序遍历如下:


[  [3],  [20,9],  [15,7]]
复制代码

解题思路

根据题意可知,此题是二叉树层序遍历的变种,我们可以用广度优先搜索的方式,对树进行层序遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度 size,每次从队列中取出 size 个元素进行拓展,然后进行下一次迭代。最后按奇偶来决定每一层的输出顺序.

代码实现

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {         Queue<TreeNode> queue = new LinkedList<>();        List<List<Integer>> res = new ArrayList<>();        if (root != null) {            queue.offer(root);        }        List<Integer> list ;        while (!queue.isEmpty()) {            int size = queue.size(); //当前层,元素的数量            list = new ArrayList<>();            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll(); //按顺序弹出队列元素,加入集合                list.add(node.val);                if (node.left != null) {                    queue.offer(node.left); //当前元素的左子树入队,即把下一层的元素加入队列                }                 if (node.right != null) {                    queue.offer(node.right); //当前元素的右子树入队,即把下一层的元素加入队列                }            }            if (res.size() % 2 == 1) { //本题中奇数层要翻转下                Collections.reverse(list);            }            res.add(list);        }        return res;    }
复制代码

最后

复杂度分析


时间复杂度:O(N),其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。


空间复杂度:O(N)。我们需要维护存储节点的队列和存储节点值的队列,空间复杂度为 O(N)。

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

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
手撸二叉树之二叉树的锯齿形层序遍历