Printing a Binary Tree in Zig Zag Level-Order | LeetCode
X. Use two stacks
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
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] ]
X. BFS
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int level = 1;
while(!q.isEmpty()){
LinkedList<Integer> path = new LinkedList<>();
int levelNums = q.size();
for(int i = 0; i < levelNums; i++){
root = q.poll();
if(level % 2 != 0){
path.add(root.val);
}else{
path.addFirst(root.val);
}
if(root.left != null)
q.offer(root.left);
if(root.right != null)
q.offer(root.right);
}
res.add(path);
level++;
}
return res;
}public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int l = 0;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node != null) {
level.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
}
if (!level.isEmpty()) {
if (l % 2 == 1) {
Collections.reverse(level);
}
ret.add(level);
}
l++;
}
return ret;
}
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean order = true;
int size = 1;
while(!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {
tmp.add(n.val);
} else {
tmp.add(0, n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
res.add(tmp);
size = q.size();
order = order ? false : true;
}
return res;
}
I use two stacks, one for processing current layer and one for storing nodes for the next layer. I also use a flag (order in your code) to indicate the direction. It is straightforward
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<List<Integer>>();
if (root == null) return output;
Stack<TreeNode> cur_layer = new Stack<TreeNode>(); cur_layer.push(root);
Stack<TreeNode> next_layer = new Stack<TreeNode>();
List<Integer> layer_output = new ArrayList<Integer>();
int d = 0; // 0: left to right; 1: right to left.
while (!cur_layer.isEmpty()){
TreeNode node = cur_layer.pop();
layer_output.add(node.val);
if(d==0){
if (node.left != null) next_layer.push(node.left);
if (node.right != null) next_layer.push(node.right);
}else{
if (node.right != null) next_layer.push(node.right);
if (node.left != null) next_layer.push(node.left);
}
if (cur_layer.isEmpty()){
output.add(layer_output);
layer_output = new ArrayList<Integer>();
cur_layer = next_layer;
next_layer = new Stack<TreeNode>();;
d ^= 1;
}
}
return output;
}
https://discuss.leetcode.com/topic/32427/java-double-stack-solution
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
if(root==null){
return result;
}
Stack<TreeNode> odd = new Stack<TreeNode>();
Stack<TreeNode> even = new Stack<TreeNode>();
even.push(root);
while(!odd.isEmpty() || !even.isEmpty()){
ArrayList<Integer> row = new ArrayList<Integer>();
if(!even.isEmpty()){
while(!even.isEmpty()){
TreeNode cur = even.pop();
row.add(cur.val);
if(cur.left!=null){
odd.push(cur.left);
}
if(cur.right!=null){
odd.push(cur.right);
}
}
}else{
while(!odd.isEmpty()){
TreeNode cur = odd.pop();
row.add(cur.val);
if(cur.right!=null){
even.push(cur.right);
}
if(cur.left!=null){
even.push(cur.left);
}
}
}
result.add(row);
}
return result;
}
X. DFS
https://discuss.leetcode.com/topic/3413/my-accepted-java-solution
- O(n) solution by using LinkedList along with ArrayList. So insertion in the inner list and outer list are both O(1),
- Using DFS and creating new lists when needed.
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level)
{
if(curr == null) return;
if(sol.size() <= level)
{
List<Integer> newLevel = new LinkedList<>();
sol.add(newLevel);
}
List<Integer> collection = sol.get(level);
if(level % 2 == 0) collection.add(curr.val);
else collection.add(0, curr.val);
travel(curr.left, sol, level + 1);
travel(curr.right, sol, level + 1);
}
}
Key Point: Using 2 stacks. O(n) time and O(n) extra space.
We can print spiral order traversal in O(n) time and O(n) extra space. The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes, and push nodes of next level in other stack.
http://algorithmsandme.com/2014/05/binary-search-tree-print-tree-in-zig-zag-order/
Method 1 (Recursive) O(n*n)
To print the nodes in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable ltr is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.
Time Complexity: Worst case time complexity of the above method is O(n^2). Worst case occurs in case of skewed trees
http://www.zrzahid.com/vertical-and-zigzag-traversal-of-binary-tree/
Read full article from Printing a Binary Tree in Zig Zag Level-Order | LeetCode
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level’s order (whether it is left->right or right->left).
You pop from stack currentLevel and print the node’s value. Whenever the current level’s order is from left->right, you push the node’s left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.
On the other hand, when the current level’s order is from right->left, you would push the node’s right child first, then its left child. Finally, don’t forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).
void printLevelOrderZigZag(BinaryTree *root) {
stack<BinaryTree*> currentLevel, nextLevel;
bool leftToRight = true;
currentLevel.push(root);
while (!currentLevel.empty()) {
BinaryTree *currNode = currentLevel.top();
currentLevel.pop();
if (currNode) {
cout << currNode->data << " ";
if (leftToRight) {
nextLevel.push(currNode->left);
nextLevel.push(currNode->right);
} else {
nextLevel.push(currNode->right);
nextLevel.push(currNode->left);
}
}
if (currentLevel.empty()) {
cout << endl;
leftToRight = !leftToRight;
swap(currentLevel, nextLevel);
}
}
}
From http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/We can print spiral order traversal in O(n) time and O(n) extra space. The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes, and push nodes of next level in other stack.
http://algorithmsandme.com/2014/05/binary-search-tree-print-tree-in-zig-zag-order/
void printSpiral(struct node *root){ if (root == NULL) return; // NULL check // Create two stacks to store alternate levels stack<struct node*> s1; // For levels to be printed from right to left stack<struct node*> s2; // For levels to be printed from left to right // Push first level to first stack 's1' s1.push(root); // Keep ptinting while any of the stacks has some nodes while (!s1.empty() || !s2.empty()) { // Print nodes of current level from s1 and push nodes of // next level to s2 while (!s1.empty()) { struct node *temp = s1.top(); s1.pop(); cout << temp->data << " "; // Note that is right is pushed before left if (temp->right) s2.push(temp->right); if (temp->left) s2.push(temp->left); } // Print nodes of current level from s2 and push nodes of // next level to s1 while (!s2.empty()) { struct node *temp = s2.top(); s2.pop(); cout << temp->data << " "; // Note that is left is pushed before right if (temp->left) s1.push(temp->left); if (temp->right) s1.push(temp->right); } }}To print the nodes in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable ltr is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.
Time Complexity: Worst case time complexity of the above method is O(n^2). Worst case occurs in case of skewed trees
void printSpiral(struct node* root){ int h = height(root); int i; /*ltr -> Left to Right. If this variable is set, then the given level is traverseed from left to right. */ bool ltr = false; for(i=1; i<=h; i++) { printGivenLevel(root, i, ltr); /*Revert ltr to traverse next level in oppposite order*/ ltr = !ltr; }}/* Print nodes at a given level */void printGivenLevel(struct node* root, int level, int ltr){ if(root == NULL) return; if(level == 1) printf("%d ", root->data); else if (level > 1) { if(ltr) { printGivenLevel(root->left, level-1, ltr); printGivenLevel(root->right, level-1, ltr); } else { printGivenLevel(root->right, level-1, ltr); printGivenLevel(root->left, level-1, ltr); } }}http://www.zrzahid.com/vertical-and-zigzag-traversal-of-binary-tree/
public static void zigzagTraversal(BTNode root){ Queue<BTNode> queue = new ArrayDeque<BTNode>(); queue.offer(root); BTNode node = null; int count = 1; int level = 0; Stack<BTNode> reverse = new Stack<BTNode>(); while(!queue.isEmpty()){ node = queue.poll(); count--; //right to left if((level&1) == 0){ reverse.push(node); } else{ System.out.print(node.key); } if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } //level ended if(count == 0){ if((level&1) == 0){ while(!reverse.isEmpty()){ System.out.print(reverse.pop().key); } } System.out.println(); count = queue.size(); level++; } } }
