Leetcode
Tree
Breath-first Search
Stack
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7]
,
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
分析¶
这道题目是LeetCode 102. Binary Tree Level Order Traversal的变形,其实增加一个判断即可,如果是从左往右,那么直接添加;如果是从右往左,那么先反转再添加。
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> zigzag = new ArrayList<>(); if (root == null) return zigzag; boolean isLeftToRight = true; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); list.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } if (isLeftToRight){ zigzag.add(list); isLeftToRight = false; } else { Collections.reverse(list); zigzag.add(list); isLeftToRight = true; } } return zigzag; }
近期评论