LeetCode Solutions

			

class Solution {
 public:
  vector<vector<int>> verticalOrder(TreeNode* root) {
    if (root == nullptr)
      return {};

    vector<int> range(2);
    getRange(root, range, 0);  // Get the leftmost and rightmost x index

    vector<vector<int>> ans(range[1] - range[0] + 1);
    queue<pair<TreeNode*, int>> q{{{root, -range[0]}}};  // (TreeNode, x)

    while (!q.empty()) {
      const auto [node, x] = q.front();
      q.pop();
      ans[x].push_back(node->val);
      if (node->left)
        q.emplace(node->left, x - 1);
      if (node->right)
        q.emplace(node->right, x + 1);
    }

    return ans;
  }

 private:
  void getRange(TreeNode* root, vector<int>& range, int x) {
    if (root == nullptr)
      return;

    range[0] = min(range[0], x);
    range[1] = max(range[1], x);

    getRange(root->left, range, x - 1);
    getRange(root->right, range, x + 1);
  }
};

			

class Solution {
  public List<List<Integer>> verticalOrder(TreeNode root) {
    if (root == null)
      return new ArrayList<>();

    List<List<Integer>> ans = new ArrayList<>();
    Queue<Pair<TreeNode, Integer>> q = new ArrayDeque<>(); // (TreeNode, x)
    int[] range = new int[2];
    getRange(root, range, 0); // Get the leftmost and rightmost x index

    for (int i = range[0]; i <= range[1]; ++i)
      ans.add(new ArrayList<>());

    q.offer(new Pair<>(root, -range[0]));

    while (!q.isEmpty()) {
      final TreeNode node = q.peek().getKey();
      final int x = q.poll().getValue();
      ans.get(x).add(node.val);
      if (node.left != null)
        q.offer(new Pair<>(node.left, x - 1));
      if (node.right != null)
        q.offer(new Pair<>(node.right, x + 1));
    }

    return ans;
  }

  private void getRange(TreeNode root, int[] range, int x) {
    if (root == null)
      return;

    range[0] = Math.min(range[0], x);
    range[1] = Math.max(range[1], x);

    getRange(root.left, range, x - 1);
    getRange(root.right, range, x + 1);
  }
}

			

class Solution:
  def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
      return []

    range_ = [0] * 2

    def getRange(root: Optional[TreeNode], x: int) -> None:
      if not root:
        return

      range_[0] = min(range_[0], x)
      range_[1] = max(range_[1], x)

      getRange(root.left, x - 1)
      getRange(root.right, x + 1)

    getRange(root, 0)  # Get the leftmost and rightmost x index

    ans = [[] for _ in range(range_[1] - range_[0] + 1)]
    q = deque([(root, -range_[0])])  # (TreeNode, x)

    while q:
      node, x = q.popleft()
      ans[x].append(node.val)
      if node.left:
        q.append((node.left, x - 1))
      if node.right:
        q.append((node.right, x + 1))

    return ans