☆打卡算法☆LeetCode 103、二叉树的锯齿形层序遍历 算法解析

举报
恬静的小魔龙 发表于 2022/04/20 08:41:58 2022/04/20
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定二叉树的根节点,返回其节点值的锯齿形层序遍历。”题目链接:来源:力扣(LeetCode)链接:103. 二叉树的锯齿形层序遍...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定二叉树的根节点,返回其节点值的锯齿形层序遍历。”

题目链接:

来源:力扣(LeetCode)

链接:103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

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

image.png

示例 1:
输入: root = [3,9,20,null,null,15,7]
输出: [[3],[20,9],[15,7]]
示例 2:
输入: root = [1]
输出: [[1]]

二、解题

1、思路分析

我发现最近几天的题目都是二叉树,是让我们彻底搞懂二叉树嘛。。。

OK,言归正传,这道题是102题二叉树的层序遍历的变化而来,只是对最后的输出有所变化,要求我们按照锯尺层序遍历。也就是从左往右遍历树节点,然后再从右向左遍历树节点。

这道题依旧可以使用102题的思路,使用广度优先搜索算法,对树进行逐层遍历,用队列去维护当前层所有元素,当队列不为空的时候,求得队列长度,每次从队列汇总取出队列长度的元素进行下一次迭代。

为了解题,我们可以使用双端队列的数据结构来维护当前层节点值输出的顺序,双端队列是一个可以在队列任意一端插入元素的队列。

那么就可以这样:

  • 如果从左向右遍历,将遍历的元素插入双端队列的尾部
  • 如果从右向左遍历,将遍历的元素插入双端队列的首部

遍历结束,就得到了我们想要的数组答案了。

2、代码实现

代码参考:

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}

image.png

3、时间复杂度

时间复杂度 : O(N)

其中N是二叉树的节点数,每个节点数都会被遍历一次。

空间复杂度: O(N)

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

三、总结

在广度优先搜索算法的基础上,区分每一层,就得到了层序遍历。

然后使用双端队列储存每个节点的值,遍历完成后,就得到了我们想要的答案了。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。