103. 二叉树的锯齿形层次遍历

/** * 103. 二叉树的锯齿形层次遍历 * @author wsq * @date 2020/10/04 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如： 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层次遍历如下： [ [3], [20,9], [15,7] ] 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal */ package com.wsq.tree; import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class ZigzagLevelOrder { /** * 使用栈和队列配合完成。效率比较低，可以做优化 * @param root * @return */ public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList(); boolean left2right = true; Deque<TreeNode> stack = new LinkedList(); Queue<TreeNode> queue = new LinkedList(); stack.push(root); while(!stack.isEmpty()){ while(!stack.isEmpty()){ queue.offer(stack.pop()); } List<Integer> tmpList = new ArrayList(); while(!queue.isEmpty()){ TreeNode tmpNode = queue.poll(); if(tmpNode == null){ continue; } tmpList.add(tmpNode.val); if(left2right){ stack.push(tmpNode.left); stack.push(tmpNode.right); }else{ stack.push(tmpNode.right); stack.push(tmpNode.left); } } if(tmpList.size() != 0){ ans.add(tmpList); } left2right = !left2right; } return ans; } }