In cây nhị phân dạng ma trận 2D trong C++

Hiển thị cây nhị phân trong ma trận chuỗi m x n theo quy tắc:

• Số hàng m = chiều cao cây.
• Số cột n luôn lẻ (2^h - 1).
• Gốc ở giữa hàng đầu. Không gian chia đôi cho cây con trái/phải.
• Ô trống chứa chuỗi rỗng.

Thuật toán (Đệ quy)

1. Tính chiều cao h, số cột leaves = 2^h - 1.
2. Khởi tạo ma trận h x leaves rỗng.
3. Hàm fill(node, ret, lvl, l, r):
   • Nếu node rỗng → return.
   • Đặt giá trị tại ret[lvl][(l+r)/2].
   • Gọi đệ quy cho con trái: fill(left, ret, lvl+1, l, (l+r)/2).
   • Gọi đệ quy cho con phải: fill(right, ret, lvl+1, (l+r+1)/2, r).

Mã nguồn C++

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

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

class Solution {
public:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(getHeight(node->left), getHeight(node->right));
    }
    void fill(TreeNode* node, vector<vector<string>>& ret, int lvl, int l, int r) {
        if (!node) return;
        ret[lvl][(l + r) / 2] = to_string(node->val);
        fill(node->left, ret, lvl + 1, l, (l + r) / 2);
        fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        int h = getHeight(root);
        int leaves = (1 << h) - 1;
        vector<vector<string>> ret(h, vector<string>(leaves, ""));
        fill(root, ret, 0, 0, leaves);
        return ret;
    }
};

Ví dụ

Cây [1,2,3,null,4] in ra ma trận 3x7 như mô tả.