Vertical Traversal of Binary Tree

0987_vertical-order-traversal-of-a-binary-tree.cs

// complexity less than n lg n

public class Solution {
  List<List<Node>> vertListPos;    // for positive
  List<List<Node>> vertListNeg;    // for negative
  List<List<Node>> vertList = null;    // pointer

  internal class Node {
    public int val { get; set; }
    public int level { get; set; }

    public Node(int val, int level) {
      this.val = val;
      this.level = level;
    }
  }

  public IList<IList<int>> VerticalTraversal(TreeNode root) {
    vertListPos = new List<List<Node>>();
    vertListNeg = new List<List<Node>>();

    VerticalTraversal(root, 0, 0);
    List<IList<int>> vertListM = new List<IList<int>>(vertListNeg.Count + vertListPos.Count);

    int j = 0;
    for (int i = vertListNeg.Count - 1; i >= 0; i--, j++) {
      vertListNeg[i].Sort((a, b) => a.level == b.level ? a.val - b.val : a.level - b.level);
      vertListM.Add(new List<int>());
      foreach (var node in vertListNeg[i])
        vertListM[j].Add(node.val);
    }

    for (int i = 0; i < vertListPos.Count; i++, j++) {
      vertListPos[i].Sort((a, b) => a.level == b.level ? a.val - b.val : a.level - b.level);
      vertListM.Add(new List<int>());
      foreach (var node in vertListPos[i])
        vertListM[j].Add(node.val);
    }

    return vertListM;
  }

  public void VerticalTraversal(TreeNode node, int index, int level) {
    if (node == null)
      return;

    var oldIndex = index;
    if (index < 0) {
      oldIndex = index;
      index = -index - 1;
      vertList = vertListNeg;
    }
    else
      vertList = vertListPos;

    if (vertList.Count == index)
      vertList.Add(new List<Node>());
    vertList[index].Add(new Node(node.val, level));
    index = oldIndex;

    VerticalTraversal(node.left, index - 1, level + 1);
    VerticalTraversal(node.right, index + 1, level + 1);
  }
}