[leetcode]103. Binary Tree Zigzag Level Order Traversal@Java解题报告

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

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] ]

package go.jacob.day806; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack; /** * * @author Jacob * 103. Binary Tree Zigzag Level Order Traversal * * 两种解法：1.使用两个堆栈；2.使用一个queue，用flag记录当前行打印顺序 */ public class Demo2 { /* * 方法一 解法与Binary Tree Level Order Traversal一致 区别是需要用一个flag判断应该正序or逆序打印 */ public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) return res; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); // 用flag控制正序或者逆序打印 boolean flag = true; while (!queue.isEmpty()) { int size = queue.size(); ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (flag) list.add(node.val); else list.add(0, node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } flag = !flag; res.add(list); } return res; } /* * 解法二 使用两个堆栈 */ public List<List<Integer>> zigzagLevelOrder_2(TreeNode root) { TreeNode c = root; List<List<Integer>> ans = new ArrayList<List<Integer>>(); if (c == null) return ans; Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); s1.push(root); while (!s1.isEmpty() || !s2.isEmpty()) { List<Integer> tmp = new ArrayList<Integer>(); while (!s1.isEmpty()) { c = s1.pop(); tmp.add(c.val); if (c.left != null) s2.push(c.left); if (c.right != null) s2.push(c.right); } ans.add(tmp); tmp = new ArrayList<Integer>(); while (!s2.isEmpty()) { c = s2.pop(); tmp.add(c.val); if (c.right != null) s1.push(c.right); if (c.left != null) s1.push(c.left); } if (!tmp.isEmpty()) ans.add(tmp); } return ans; } private class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }