Binary Tree Vertical Order Traversal

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 241 ms)

Metric	Value
Runtime	241 ms
Memory	42.2 MB
Date	2022-02-23

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
    if (root == null) return result;
    Queue<(TreeNode, int)> q = new Queue<(TreeNode, int)>();
    Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();
    q.Enqueue((root, 0));
    int min = 0, max = 0;
    int row = 0;
    while (q.Count != 0)
    {
            var front = q.Dequeue();
            var node = front.Item1;
            var col = front.Item2;
            
            if (map.ContainsKey(col)) 
                map[col].Add(node.val);
            else 
                map.Add(col, new List<int>() {node.val});
                
            if (node.left != null)
            {
                min = Math.Min(min, col - 1);
                q.Enqueue((node.left, col - 1));
            }
            if (node.right != null)
            {
                max = Math.Max(max, col + 1);
                q.Enqueue((node.right, col + 1));
            }
    }
    for (int i = min; i <= max; i++)
    {
        if (!map.ContainsKey(i)) continue;
        result.Add(map[i]);
    }
    return result;
}
}

📜 1 more C# submission(s)

Submission (2022-02-23) — 327 ms, 42.3 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
    if (root == null) return result;
    Queue<(TreeNode, int)> q = new Queue<(TreeNode, int)>();
    Dictionary<int, List<int[]>> map = new Dictionary<int, List<int[]>>();
    q.Enqueue((root, 0));
    int min = 0, max = 0;
    int row = 0;
    while (q.Count != 0)
    {
        int levelSize = q.Count;
        for (int j = 0; j < levelSize; j++)
        {
            var front = q.Dequeue();
            var node = front.Item1;
            var col = front.Item2;
            
            if (map.ContainsKey(col)) 
                map[col].Add(new int[] { row, col, node.val });
            else 
                map.Add(col, new List<int[]>() { new int[] { row, col, node.val } });
                
            if (node.left != null)
            {
                min = Math.Min(min, col - 1);
                q.Enqueue((node.left, col - 1));
            }
            if (node.right != null)
            {
                max = Math.Max(max, col + 1);
                q.Enqueue((node.right, col + 1));
            }
        }
        row++;
    }
    for (int i = min; i <= max; i++)
    {
        if (!map.ContainsKey(i)) continue;
        map[i].Sort(new VerticalComparer());
        result.Add(map[i].Select(x => x[2]).ToList());
    }
    return result;
}

public class VerticalComparer : IComparer<int[]>
{
    public int Compare(int[] x, int[] y)
    {
        // if row is equal compare value
        if (x[0] == y[0]) return x[1].CompareTo(y[1]);
        else
            return x[0].CompareTo(y[0]);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed