【leetcode】【2022/8/22】655. 输出二叉树

问题描述：

• 给定一棵二叉树的根节点 root，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res，用以表示树的格式化布局。
• 构造此格式化布局矩阵需要遵循以下规则：
  • 树的高度为 height，矩阵的行数 m 应该等于 height + 1。
  • 矩阵的列数 n 应该等于 2^{height+1} - 1。
  • 根节点需要放置在顶行的正中间，对应位置为 res[0][(n-1)/2]。
  • 对于放置在矩阵中的每个节点，设对应位置为 res[r][c]，将其左子节点放置在 res[r+1][c-2^{height-r-1}]，右子节点放置在 res[r+1][c+2^{height-r-1}]。
  • 继续这一过程，直到树中的所有节点都妥善放置。
  • 任意空单元格都应该包含空字符串 ""。
  • 返回构造得到的矩阵 res。

核心思路：

• 同样的谜面就是谜底，跟随题意进行模拟即可。
• 先通过层次遍历确认树的高度，从而建立结果数组，紧接着再通过递归遍历就可以在结果数组对应位置上设置字符串。

代码实现：

class Solution
{
private:
    int findHeight(TreeNode* root) // root一定非空
    {
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        while(!q.empty())
        {
            int sz = q.size();
            while(sz-- > 0)
            {
                TreeNode* tmp = q.front(); q.pop();
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ++level;
        }
        return level;
    }
    void dfsprintTree(TreeNode* root, vector<vector<string>>& tree, int r, int c, int h)
    {
        if(!root) return;
        tree[r][c] = to_string(root->val);
        dfsprintTree(root->left, tree, r+1, c-pow(2, h-r-1), h);
        dfsprintTree(root->right, tree, r+1, c+pow(2, h-r-1), h);
        return;
    }
public:
    vector<vector<string>> printTree(TreeNode* root)
    {
        int height = findHeight(root);
        int m = height;
        int n = pow(2, m)-1;
        vector<vector<string>> tree(m, vector<string>(n));
        dfsprintTree(root, tree, 0, (n-1)/2, m-1);
        return tree;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40