题解 | 超级圣诞树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 递归绘制一个 n 级子树，其底部中心位于 (bottom_row, center_col)
void draw_subtree(int n, int bottom_row, int center_col, char** matrix) {
    if (n == 1) {
        // n=1 的三角形：高度 3，底部宽度 5
        matrix[bottom_row - 2][center_col] = '*';                 // 第0行
        matrix[bottom_row - 1][center_col - 1] = '*';            // 第1行左
        matrix[bottom_row - 1][center_col + 1] = '*';            // 第1行右
        matrix[bottom_row][center_col - 2] = '*';                // 第2行最左
        matrix[bottom_row][center_col] = '*';                    // 第2行中
        matrix[bottom_row][center_col + 2] = '*';                // 第2行最右
        return;
    }

    int h = 3 * (1 << (n - 2));      // 上一级子树的高度
    // 1. 上半部分子树（n-1 级），底部位于当前底部正上方 h 行
    draw_subtree(n - 1, bottom_row - h, center_col, matrix);
    // 2. 下半部分左子树（n-1 级），底部位于当前底部，中心左移 h 列
    draw_subtree(n - 1, bottom_row, center_col - h, matrix);
    // 3. 下半部分右子树（n-1 级），底部位于当前底部，中心右移 h 列
    draw_subtree(n - 1, bottom_row, center_col + h, matrix);
}

int main() {
    int n;
    scanf("%d", &n);

    // 树冠高度 H = 3 * 2^(n-1)
    int H = 3 * (1 << (n - 1));
    int total_rows = H + n;                 // 树冠 + 树干
    int total_cols = 2 * H - 1;             // 最大宽度（树冠底部）
    int center = H - 1;                     // 中心列索引（0‑based）

    // 动态分配二维字符数组（初始化为空格）
    char** grid = (char**)malloc(total_rows * sizeof(char*));
    for (int i = 0; i < total_rows; i++) {
        grid[i] = (char*)malloc(total_cols * sizeof(char));
        memset(grid[i], ' ', total_cols);
    }

    // 绘制树冠
    draw_subtree(n, H - 1, center, grid);

    // 绘制树干（n 行，每行一个星号，位于中心列）
    for (int i = 0; i < n; i++) {
        grid[H + i][center] = '*';
    }

    // 输出结果，每行只输出到最后一个星号的位置
    for (int r = 0; r < total_rows; r++) {
        int last = -1;
        // 从右向左寻找该行最后一个星号
        for (int c = total_cols - 1; c >= 0; c--) {
            if (grid[r][c] == '*') {
                last = c;
                break;
            }
        }
        if (last != -1) {
            for (int c = 0; c <= last; c++) {
                putchar(grid[r][c]);
            }
        }
        putchar('\n');
    }

    // 释放内存
    for (int i = 0; i < total_rows; i++) {
        free(grid[i]);
    }
    free(grid);

    return 0;
}