题目描述

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：

行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串”“。
使用相同的规则输出子树。

样例

输入:
     1
    /
   2
输出:
[["", "1", ""],
 ["2", "", ""]]

 输入:
     1
    / \
   2   3
    \
     4
输出:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

 输入:
      1
     / \
    2   5
   / 
  3 
 / 
4 
输出:
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

算法1

设树高为h，由题意易得输出的二维字符串数组vector<vector<string>>ans由h个字符串数组组成，其中每个字符串数组有2^h - 1个字符串，将ans每个元素初始化为""。

由题意易得，每次处理结点时居中放即可，然后两边递归。

时间复杂度 $O(h*2^h)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getdepth(TreeNode* root){
        if(!root)return 0;
        else return max(getdepth(root->left),getdepth(root->right)) + 1;
    }
    void print(TreeNode* root,vector<vector<string>>&ans,int l,int r,int level){
        if(!root)return;
        ans[level][(l + r)>>1] = to_string(root->val);
        print(root->left,ans,l,l + (r - l)/2,level + 1);
        print(root->right,ans,l + (r-l + 1)/2,r,level + 1);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        vector<vector<string>>ans;
        int h = getdepth(root);
        for(int i =0;i < h;++i){
            vector<string>t;
            for(int j = 0;j < (2<<(h- 1)) - 1;++j){
                t.push_back("");
            }
            ans.push_back(t);
        }
        print(root,ans,0,(2<<(h - 1))-1,0);
        return ans;
    }
};

```