314. Binary Tree Vertical Order Traversal

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        IList<IList<int>> output = new List<IList<int>>();
        if (root == null) {
            return output;
        }
        Dictionary<int, List<int>> columnTable = new Dictionary<int, List<int>>();
        Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
        int column = 0;
        queue.Enqueue((root, column));
        while (queue.Count > 0) {
            var (node, col) = queue.Dequeue();
            if (node != null) {
                if (!columnTable.ContainsKey(col)) {
                    columnTable[col] = new List<int>();
                }
                columnTable[col].Add(node.val);
                queue.Enqueue((node.left, col - 1));
                queue.Enqueue((node.right, col + 1));
            }
        }
        var sortedKeys = new List<int>(columnTable.Keys);
        sortedKeys.Sort();
        foreach (var key in sortedKeys) {
            output.Add(columnTable[key]);
        }
        return output;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    public IList<vector<int>> VerticalOrder(TreeNode root) {
        IList<vector<int>> output = new List<vector<int>>();
        if (root == null) {
            return output;
        }
        unordered_map<int, List<int>> columnTable = new unordered_map<int, List<int>>();
        queue<(TreeNode, int)> queue = new queue<(TreeNode, int)>();
        int column = 0;
        queue.Enqueue((root, column));
        while (queue.size() > 0) {
            var (node, col) = queue.Dequeue();
            if (node != null) {
                if (!columnTable.count(col)) {
                    columnTable[col] = new List<int>();
                }
                columnTable[col].push_back(node.val);
                queue.Enqueue((node.left, col - 1));
                queue.Enqueue((node.right, col + 1));
            }
        }
        var sortedKeys = new List<int>(columnTable.Keys);
        sortedKeys.Sort();
        foreach (var key in sortedKeys) {
            output.push_back(columnTable[key]);
        }
        return output;
    }
}

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

        Map<Integer, ArrayList<Integer>> columnTable = new HashMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
        int column = 0;
        queue.offer(new Pair<>(root, column));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            root = p.getKey();
            column = p.getValue();

            if (root != null) {
                if (!columnTable.containsKey(column)) {
                    columnTable.put(column, new ArrayList<Integer>());
                }
                columnTable.get(column).add(root.val);

                queue.offer(new Pair<>(root.left, column - 1));
                queue.offer(new Pair<>(root.right, column + 1));
            }
        }

        List<Integer> sortedKeys = new ArrayList<>(columnTable.keySet());
        Collections.sort(sortedKeys);
        for (int k : sortedKeys) {
            output.add(columnTable.get(k));
        }

        return output;
    }
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    verticalOrder(root) {
        const output = [];
        if (root === null) {
            return output;
        }

        const columnTable = new Map();
        const queue = [];
        let column = 0;
        queue.push([root, column]);

        while (queue.length > 0) {
            const [node, col] = queue.shift();

            if (node !== null) {
                if (!columnTable.has(col)) {
                    columnTable.set(col, []);
                }
                columnTable.get(col).push(node.val);

                queue.push([node.left, col - 1]);
                queue.push([node.right, col + 1]);
            }
        }

        const sortedKeys = Array.from(columnTable.keys()).sort((a, b) => a - b);
        for (const key of sortedKeys) {
            output.push(columnTable.get(key));
        }

        return output;
    }
}

from collections import defaultdict
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        columnTable = defaultdict(list)
        queue = deque([(root, 0)])

        while queue:
            node, column = queue.popleft()

            if node is not None:
                columnTable[column].append(node.val)
                
                queue.append((node.left, column - 1))
                queue.append((node.right, column + 1))
                        
        return [columnTable[x] for x in sorted(columnTable.keys())]

package main

import (
    "sort"
    "container/list"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func verticalOrder(root *TreeNode) [][]int {
    var output [][]int
    if root == nil {
        return output
    }

    columnTable := map[int][]int{}
    queue := list.New()
    queue.PushBack([2]interface{}{root, 0})

    for queue.Len() > 0 {
        element := queue.Front()
        queue.Remove(element)
        pair := element.Value.([2]interface{})
        node := pair[0].(*TreeNode)
        column := pair[1].(int)

        if node != nil {
            columnTable[column] = append(columnTable[column], node.Val)

            if node.Left != nil {
                queue.PushBack([2]interface{}{node.Left, column - 1})
            }
            if node.Right != nil {
                queue.PushBack([2]interface{}{node.Right, column + 1})
            }
        }
    }

    var sortedKeys []int
    for key := range columnTable {
        sortedKeys = append(sortedKeys, key)
    }
    sort.Ints(sortedKeys)

    for _, key := range sortedKeys {
        output = append(output, columnTable[key])
    }

    return output
}

Explanation

Algorithm

1️⃣

Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2️⃣

Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3️⃣

После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎