Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //BFS solution
- //Time: O(n), 2ms
- //Space: O(h)
- class Solution {
- public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
- List<List<Integer>> ans = new ArrayList<>();
- if(root == null) return ans;
- Queue<TreeNode> q = new LinkedList<>();
- q.offer(root);
- int depth = 1;
- while(!q.isEmpty()) {
- int size = q.size();
- LinkedList<Integer> list = new LinkedList<>();
- for(int i = 0; i < size; i++) {
- TreeNode node = q.poll();
- if(depth % 2 == 1) {
- list.add(node.val);
- } else {
- list.addFirst(node.val);
- }
- if(node.left != null) q.offer(node.left);
- if(node.right != null) q.offer(node.right);
- }
- ans.add(list);
- depth++;
- }
- return ans;
- }
- }
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
Add Comment
Please, Sign In to add comment