题目
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,#,#,15,7}
,
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]分析
从遍历顺序上看,直接想到BFS和栈,实现时遍历顺序还是需要耐心确认的。
代码
import java.util.ArrayList; import java.util.Stack; public class BinaryTreeZigzagLevelOrderTraversal { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (root == null) { return results; } Stack<TreeNode> currentLevel = new Stack<TreeNode>(); Stack<TreeNode> nextLevel = new Stack<TreeNode>(); boolean reverse = false; ArrayList<Integer> list = new ArrayList<Integer>(); currentLevel.push(root); while (!currentLevel.isEmpty()) { TreeNode node = currentLevel.pop(); list.add(node.val); if (reverse) { if (node.right != null) { nextLevel.push(node.right); } if (node.left != null) { nextLevel.push(node.left); } } else { if (node.left != null) { nextLevel.push(node.left); } if (node.right != null) { nextLevel.push(node.right); } } if (currentLevel.isEmpty()) { Stack<TreeNode> temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; results.add(new ArrayList<Integer>(list)); list.clear(); reverse = !reverse; } } return results; } }
LeetCode | Binary Tree Zigzag Level Order Traversal,布布扣,bubuko.com
LeetCode | Binary Tree Zigzag Level Order Traversal
原文:http://blog.csdn.net/perfect8886/article/details/20306335