1. 题目
给你二叉树的根节点 root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
1 2
| 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[20,9],[15,7]]
|
示例 2:
示例 3:
提示:
- 树中节点数目在范围
[0, 2000]
内
-100 <= Node.val <= 100
2. 思路
- 已知题目要求进行二叉树的层序遍历,配合着锯齿形的遍历方式
- 在原先的二叉树层序遍历基础上,引入一个变量用于记录当前的遍历方式是正序还是逆序
3. 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { if (root == null) { return List.of(); }
var result = new ArrayList<List<Integer>>(); var queue = new ArrayDeque<TreeNode>(); queue.offer(root); var flag = true;
while (!queue.isEmpty()) { var size = queue.size(); var list = new ArrayList<Integer>();
for (var i = 0; i < size; ++i) { var node = queue.poll(); list.add(node.val);
if (node.left != null) { queue.offer(node.left); }
if (node.right != null) { queue.offer(node.right); } }
if (!flag) { Collections.reverse(list); }
flag = !flag; result.add(list);
}
return result; } }
|
4. 复杂度
Author:
zchengb
License:
Copyright (c) 2019-2024 zchengb