leetcode 655 输出二叉树

leetcode 655 输出二叉树

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

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

分析

• 使用层次遍历二叉树
• 需要先获取二叉树的高度，以便构造容器
• 每层中的节点值都放置到特定位置

  已知2个index，l 和r, 当前节点放置到 中间位置m = (l+r)/2;
  左子树的放置范围为[l,m)
  右子树的放置范围为（m,r],也即是[m+1,r]

code

class Solution {
    int Height(TreeNode* root){
        if(!root) return -1;
        auto l = Height(root->left);
        auto r = Height(root->right);
        return max(l,r)+1;
    }
    void levelOrder(TreeNode* root,vector<vector<string>>& res,int level,int l,int r){
        if(!root) return;
        int m = (l+r)/2;
        res[level][m] = to_string(root->val);
        levelOrder(root->left,res,level+1,l,m);
        levelOrder(root->right,res,level+1,m+1,r);
    }
public:
    vector<vector<string>> printTree(TreeNode* root) {
        int h = Height(root);
        int m = pow(2,h+1) - 1;
        vector<vector<string>> res(h+1,vector<string>(m));
        levelOrder(root,res,0,0,m-1);
        return res;
    }
};