655. 输出二叉树

题目：

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

树的 高度 为 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] 。
继续这一过程，直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 "" 。
返回构造得到的矩阵 res 。

---

示例 1:

输入：root = [1,2]
输出：
[["","1",""],
 ["2","",""]]

---

示例 2：

输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
 ["","2","","","","3",""],
 ["","","4","","","",""]]

---

提示：

树中节点数在范围 [1, 210] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/print-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

1.先要确定结果的行数（既是二叉树高度）与列数（既是二叉树的宽度），先输出一个空的字符串二维vector。
2.遍历二叉树，将遍历到的二叉树的节点确定它在二维vector的位置，其行数由此时节点高度确定，列数由二叉树的边界范围的中值确定。
3.当二叉树遍历完成，那么修改就完成了。

---

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector> res;
    vector> printTree(TreeNode* root) {
        int m = height(root);
        int n = pow(2, m) -1;
        // 二维vector一致填充好
        for (int i=0; i
            vector temp;
            for (int i=0; i
                temp.push_back("");
            }
            res.push_back(temp);
        }
        fill(root, 0, 0, n-1);
        return res;
    }
 
    void fill(TreeNode* root, int depth, int begin, int end){
        if (!root) return;
        int mid = begin + (end-begin)/2;
        res[depth][mid] = to_string(root->val);
        fill(root->left, depth+1, begin, mid-1);
        fill(root->right, depth+1, mid+1, end);
    }
 
    int height(TreeNode* root){
        if (!root) return 0;
        return max(height(root->left), height(root->right))+1;
    }
};