【LeetCode每日一题】655.输出二叉树

题目链接：https://leetcode.cn/problems/print-binary-tree/

题目难度：中等

题意

给你一棵二叉树的根节点 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 。

示例1：

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

示例2：

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

提示：

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

题解：dfs

首先dfs遍历一遍树，获得树的高度，然后求出矩阵的行数和列数

第二遍dfs遍历过程中往矩阵中填值即可

C++代码

/**
 * 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<vector<string>> ans;
    //获得树的高度
    int height;
    void get_depth(TreeNode* root,int depth){
        if(root==nullptr) return ;
        height=max(height,depth);
        get_depth(root->left,depth+1);
        get_depth(root->right,depth+1);
    }
    //构造矩阵
    void build_matrix(TreeNode* root,int r,int c){
        if(root==nullptr) return ;
        if(root->left!=nullptr){
            ans[r+1][c-pow(2,height-r-1)] = to_string(root->left->val);
            build_matrix(root->left,r+1,c-pow(2,height-r-1));
        }
        if(root->right!=nullptr){
            ans[r+1][c+pow(2,height-r-1)] = to_string(root->right->val);
            build_matrix(root->right,r+1,c+pow(2,height-r-1));
        }
    }
    vector<vector<string>> printTree(TreeNode* root) {
        height=0;
        get_depth(root,0);
        int m=height+1, n=pow(2,height+1)-1;
        // cout<<m<<"---"<<n<<endl;

        ans = vector<vector<string>> (m,vector<string>(n,""));
        ans[0][(n-1)/2] = to_string(root->val);
        build_matrix(root,0,(n-1)/2);
        return ans;
    }
};