链接：https://leetcode.cn/problems/print-binary-tree/solution/by-xun-ge-v-b3sf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于树的相关问题->递归基本上都可以解决
题目已经给了我们解题步骤：
构造此格式化布局矩阵需要遵循以下规则：

• 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
• 矩阵的列数 n 应该等于 2height+1 - 1 。
• 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
• 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
• 继续这一过程，直到树中的所有节点都妥善放置。
• 任意空单元格都应该包含空字符串 "" 。

根据此步骤一步一步实现即可

具体实现:

• 先递归求出树的高度height
• 然后根据高度构造m x n 的字符串矩阵 ans，并全部初始化为空字符串 ""
• 然后递归遍历树的每一个节点，将头节点放置在 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
• 继续这一过程，直到树中的所有节点都妥善放置。

实现细节：
对于2^(height+1)，相信很多人都觉得头疼，难处理。可以利用位运算 << 按位左移进行简化运算
1<<2 = 1 * 2^2

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX(a , b) ((a) > (b) ? (a) : (b))
int TreeHdight(struct TreeNode * root)
{
    if(!root)
        return -1;
    return MAX(TreeHdight(root->left) , TreeHdight(root->right)) + 1;
}
//递归遍历树的每一个节点
void dfs(struct TreeNode * root, char *** ans, int r, int c, int hdight)
{
    if(!root)
        return;
    sprintf(ans[r][c], "%d", root->val);//将头节点放置在 res[r][c]
    dfs(root->left, ans, r + 1, c - (1<<abs(hdight-r-1)), hdight);//将其左子节点放置在 res[r+1][c-2height-r-1]
    dfs(root->right, ans, r + 1, c + (1<<abs(hdight-r-1)), hdight);//右子节点放置在 res[r+1][c+2height-r-1]
    return;
}
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
char *** printTree(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int hdight = TreeHdight(root);//递归求出树的高度height
    char *** ans = (char ***)malloc(sizeof(char **) * (hdight + 1));
    *returnSize = hdight+1;
    *returnColumnSizes = (char *)malloc(sizeof(int) * (hdight + 1));
    for(int i = 0; i <= hdight; i++)//然后根据高度构造m x n 的字符串矩阵 ans，并全部初始化为空字符串 ""
    {
        ans[i] = (char **)malloc(sizeof(char *) * ((1<<(hdight+1)) - 1));
        for(int j = 0; j < ((1<<(hdight+1)) - 1); j++)
        {
            ans[i][j] = (char *)calloc(5, sizeof(char));
        }
        (*returnColumnSizes)[i] = (1<<(hdight+1)) - 1;
    }
    int n = (1<<(hdight+1)) - 1;
    dfs(root, ans, 0, (n-1)/2, hdight);
    return ans;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/print-binary-tree/solution/by-xun-ge-v-b3sf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。