-
-
Save InterviewBytes/821733a0e83971a45d586bc52d40a752 to your computer and use it in GitHub Desktop.
ZigZag level order travsersal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.interviewbytes.trees; | |
public class TreeNode { | |
int val; | |
TreeNode left; | |
TreeNode right; | |
TreeNode(int x) { | |
val = x; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.interviewbytes.trees; | |
import java.util.*; | |
public class ZigZagLevelOrder { | |
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { | |
List<List<Integer>> list = new ArrayList<>(); | |
Deque<TreeNode> queue = new LinkedList<>(); | |
if (root != null) queue.offer(root); | |
boolean reverse = false; | |
while (!queue.isEmpty()) { | |
int size = queue.size(); | |
List<Integer> level = new ArrayList<>(); | |
while (size > 0) { | |
TreeNode node = queue.poll(); | |
level.add(node.val); | |
if (node.left != null) queue.offer(node.left); | |
if (node.right != null) queue.offer(node.right); | |
size--; | |
} | |
if (reverse) Collections.reverse(level); | |
list.add(level); | |
reverse = !reverse; | |
} | |
return list; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment