本文主要是介绍【力扣每日一题】力扣103二叉树的锯齿形层序遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目来源
力扣103二叉树的锯齿形层序遍历
题目概述
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
思路分析
因为每层遍历都需要换方向,我们只需要把层序遍历的顺序反过来就可以实现对父节点列表的反向遍历,增加一个标记,每轮遍历完成后反转,就可以实现对左右子节点的方向变换。
代码实现
java实现
public class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}// 父节点列表List<TreeNode> parentList = new ArrayList<>();parentList.add(root);// 子节点遍历方向标记boolean direction = false;while (!parentList.isEmpty()) {// 孩子节点列表List<TreeNode> sonList = new ArrayList<>();for (int i = parentList.size() - 1; i >= 0; i--) {TreeNode parent = parentList.get(i);if (direction) {if (parent.left != null) {sonList.add(parent.left);}if (parent.right != null) {sonList.add(parent.right);}}else {if (parent.right != null) {sonList.add(parent.right);}if (parent.left != null) {sonList.add(parent.left);}}}direction = !direction;res.add(parentList.stream().map(node -> node.val).collect(Collectors.toList()));parentList = sonList;}return res;}
}
这篇关于【力扣每日一题】力扣103二叉树的锯齿形层序遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!