For example:
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ./** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { // Similar to levelorder traversal // However, we adopt reverse row elements every second time List<List<Integer>> result = new LinkedList<>(); if (root == null) return result; List<Integer> row = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); boolean bReverse = false; // If true, reverse the row elements int count = 0; int curMode = 1; // Number of nodes of current level int nxtMode = 0; // Number of nodes of next level queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.remove(); row.add(node.val); count++; // Verify if current node is the last node of the level or not if (count%curMode == 0) { if (bReverse) { reverse(row); bReverse = false; } else bReverse = true; result.add(row); row = new LinkedList<>(); count = 0; } if (node.left != null) { queue.add(node.left); nxtMode++; // Count the number of next level node } if (node.right != null) { queue.add(node.right); nxtMode++; } // When reached the end of the level, assign next mode to current mode. // Next mode then reset to 0. if (count == 0) { curMode = nxtMode; nxtMode = 0; } } return result; } private void reverse(List<Integer> row) { int n = row.size(); for (int i = 0; i < n/2; i++) { int tmp = row.get(i); row.set(i, row.get(n-i-1)); row.set(n-i-1, tmp); } } }
No comments:
Post a Comment