Binary Tree Zigzag Level Order Traversal

-
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

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 [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

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more