Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Solution:
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] ]
Solution:
- Level-traversal using a Queue + DFS
- On enqueue put the elements on a list
- Apply list.reverse for the odd-levels
Works fast. Code's below, cheers, ACC.
public class Solution
{
public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
{
if (root == null) return new List<IList<int>>();
List<IList<int>> retVal = new List<IList<int>>();
Queue<QueueItem> queue = new Queue<QueueItem>();
QueueItem qi = new QueueItem(root, 0);
int currentLevel = 0;
queue.Enqueue(qi);
List<int> currentList = new List<int>();
int count = 0;
while (queue.Count > 0)
{
QueueItem currentItem = queue.Dequeue();
if (currentLevel < currentItem.level)
{
if (count % 2 == 1)
{
currentList.Reverse();
}
retVal.Add(currentList);
currentList = new List<int>();
count++;
}
currentLevel = currentItem.level;
currentList.Add(currentItem.node.val);
if (currentItem.node.left != null)
{
QueueItem nextItem = new QueueItem(currentItem.node.left, currentItem.level + 1);
queue.Enqueue(nextItem);
}
if (currentItem.node.right != null)
{
QueueItem nextItem = new QueueItem(currentItem.node.right, currentItem.level + 1);
queue.Enqueue(nextItem);
}
}
if (currentList.Count > 0)
{
if (count % 2 == 1)
{
currentList.Reverse();
}
retVal.Add(currentList);
}
return retVal;
}
}
public class QueueItem
{
public TreeNode node = null;
public int level = 0;
public QueueItem(TreeNode node, int level)
{
this.node = node;
this.level = level;
}
}
Comments
Post a Comment
[γγ¬γΌγ ]