首页 / 算法 / 二叉树的锯齿形层序遍历(Java实现)
二叉树的锯齿形层序遍历(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的锯齿形层序遍历(Java实现)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1642字，纯文字阅读大概需要3分钟。
内容图文
题目
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例
给定二叉树 [3,9,20,null,null,15,7],
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
Java代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) { //二叉树为空，直接返回空结果
return res;
}
ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();
deque.add(root);
leverOrder(res, deque, 1);
return res;
}
/*
* 参数列表说明：
* res 结果集
* deque 双向队列存储当前层次遍历的结点
* flag 记录当前遍历的层数，用来控制层序遍历的方向
*/
void leverOrder(List<List<Integer>> res,ArrayDeque<TreeNode> deque,int flag) {
int size = deque.size();
if(size == 0) {
return;
}
ArrayList<Integer> arrayList = new ArrayList<Integer>();
if(flag == 1) {
while(size-- != 0) {
TreeNode root = deque.pollFirst();
arrayList.add(root.val);
if(root.left != null) {
deque.offer(root.left);
}
if(root.right != null) {
deque.offer(root.right);
}
}
//加入结果集，递归下一层
res.add(arrayList);
leverOrder(res, deque, 2);
}else {
while(size-- != 0) {
TreeNode root = deque.pollLast();
arrayList.add(root.val);
if(root.right != null) {
deque.offerFirst(root.right);
}
if(root.left != null) {
deque.offerFirst(root.left);
}
}
//加入结果集，//递归下一层
res.add(arrayList);
leverOrder(res, deque, 1);
}
}
}
原文：https://www.cnblogs.com/fyy-f/p/14172136.html
内容总结
以上是互联网集市为您收集整理的二叉树的锯齿形层序遍历(Java实现)全部内容，希望文章能够帮你解决二叉树的锯齿形层序遍历(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。