พิมพ์ต้นไม้แบบทวิภาคในรูปแบบ 2D String Array ใน C++

แสดงต้นไม้แบบทวิภาคในอาร์เรย์สตริง 2 มิติขนาด m×n ตามกฎ:

• จำนวนแถว m = ความสูงของต้นไม้
• จำนวนคอลัมน์ n = เลขคี่เสมอ
• รากอยู่กลางแถวแรกพอดี พื้นที่ที่เหลือแบ่งเป็นซ้าย-ล่างและขวา-ล่างขนาดเท่ากัน
• พิมพ์ subtree ซ้ายในส่วนซ้าย-ล่าง และ subtree ขวาในส่วนขวา-ล่าง
• ช่องว่างเติมสตริงว่าง

ตัวอย่างต้นไม้ input และ output แสดงในตาราง

วิธีแก้ปัญหา (DFS + Pre-calculate Position)

1. สร้างฟังก์ชัน fill(node, ret, lvl, l, r):
   • ถ้า node เป็น null → return
   • ret[lvl][(l+r)/2] = ค่าของ node
   • fill(left, ret, lvl+1, l, (l+r)/2)
   • fill(right, ret, lvl+1, (l+r+1)/2, r)
2. จาก main:
   • h = ความสูงต้นไม้
   • leaves = 2^h - 1
   • สร้างเมทริกซ์ h × leaves เติมสตริงว่าง
   • fill(root, ret, 0, 0, leaves)
   • คืนค่า ret

ตัวอย่างโค้ด C++

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

void print_vector(vector<vector<string>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

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

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 || node->val == 0) 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;
    }
};

int main() {
    // ตัวอย่างการสร้างต้นไม้และทดสอบ
    return 0;
}

Input

[1,2,3,null,4]

Output

[[, , , 1, , , , ], [, 2, , , , 3, , ], [, , 4, , , , , ],]