Binary Tree Vertical Order Traversal - Duyệt dọc cây nhị phân

Cho cây nhị phân, trả về duyệt theo cột dọc (vertical order). Nút cùng hàng và cột: thứ tự từ trái sang phải.

Ví dụ: cây [3,9,20,null,null,15,7] → [[9],[3,15],[20],[7]].

Giải thuật (BFS với tọa độ cột)

Duyệt BFS, gán tọa độ cột x (gốc = 0, trái = x-1, phải = x+1). Dùng map x -> list giá trị. BFS đảm bảo thứ tự hàng (top-down) và trái-phải. Cuối cùng lấy giá trị map theo thứ tự key tăng dần.

Cài đặt C++

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

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (auto& row : v) {
        cout << "[";
        for (int val : row) cout << val << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

class Solution {
public:
    map<int, vector<int>> m;

    void solve(TreeNode* node, int x = 0) {
        if (!node || node->val == 0) return;
        solve(node->left, x - 1);
        solve(node->right, x + 1);
        m[x].push_back(node->val);
    }

    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        queue<pair<int, TreeNode*>> q;
        q.push({0, root});
        m[0].push_back(root->val);
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto curr = q.front(); q.pop();
                TreeNode* node = curr.second;
                int x = curr.first;
                if (node->left && node->left->val != 0) {
                    q.push({x - 1, node->left});
                    m[x - 1].push_back(node->left->val);
                }
                if (node->right && node->right->val != 0) {
                    q.push({x + 1, node->right});
                    m[x + 1].push_back(node->right->val);
                }
            }
        }
        vector<vector<int>> ret;
        for (auto& it : m) ret.push_back(it.second);
        return ret;
    }
};

int main() {
    Solution ob;
    // Tree construction omitted
    return 0;
}

Đầu vào

{3,9,20,NULL,NULL,15,7}

Đầu ra

[[9, ],[3, 15, ],[20, ],[7, ],]