题目链接: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:

print1-tree-2022-09-11-18-33-11

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

示例2:

print2-tree-2022-09-11-18-33-25

输入: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;
    }
};