栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【日常训练】103. 二叉树的锯齿形层序遍历

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【日常训练】103. 二叉树的锯齿形层序遍历

题目

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

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]

示例 2:
输入:root = [1]
输出:[[1]]

示例 3:
输入:root = []
输出:[]

提示:
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

代码
package dayLeetCode;

import java.util.*;

public class dayleetcode103 {
    // bfs 为了维护从左往右和从右往左遍历 需要使用双端队列
    // 层次遍历 根左右
    public List> zigzagLevelOrder(TreeNode root) {
        List> ansList = new LinkedList>();

        if(root == null){
            return ansList;
        }

        Queue queue = new ArrayDeque();
        queue.offer(root);
        // 用来标记当前是从左往右还是从右往左
        boolean leftFlag = true;

        while(!queue.isEmpty()){
            Deque levelQueue = new LinkedList();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode curNode = queue.poll();
                // 从左往右,将该元素从队尾加入队列
                if(leftFlag){
                    levelQueue.offerLast(curNode.val);
                }
                // 从右往左,将该元素从队首加入队列
                else{
                    levelQueue.offerFirst(curNode.val);
                }

                if(curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
            }

            for(int num : levelQueue){
                System.out.println(num);
            }

            ansList.add(new LinkedList(levelQueue));
            leftFlag = !leftFlag;
        }
        return ansList;
    }
    
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981201.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号