LeetCode 655. 输出二叉树（二叉树高度&二叉树遍历）

Michael阿明

发布于 2020-07-13 16:06:11

4440

发布于 2020-07-13 16:06:11

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

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

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

示例 1:
输入:
     1
    /
   2
输出:
[["", "1", ""],
 ["2", "", ""]]
 
示例 2:
输入:
     1
    / \
   2   3
    \
     4
输出:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]
 
示例 3:
输入:
      1
     / \
    2   5
   / 
  3 
 / 
4 
输出:
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]
注意: 二叉树的高度在范围 [1, 10] 中。

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

2. 解题

先求二叉树高度height
根据高度知道列的宽度width = 2^height - 1
递归在区间中点填入节点的val的string格式

class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        int height = getHeight(root);//求高度
        int width = (2<<(height-1))-1;//确定宽度
        vector<vector<string>> ans(height,vector<string> (width,""));
        dfs(ans,root,0,0,width-1);
        return ans;
    }

    int getHeight(TreeNode* root)//递归求高度
    {
    	if(root == NULL)
    		return 0;
    	return max(getHeight(root->left),getHeight(root->right))+1;
    }

    void dfs(vector<vector<string>> &ans, TreeNode* root, int f, int L, int R)
    {
    	if(root == NULL)
    		return;
    	int mid = ((L+R)>>1);//区间中点
    	ans[f][mid] = to_string(root->val);//f深度
    	dfs(ans,root->left,f+1,L,mid-1);//递归填充左右侧
    	dfs(ans,root->right,f+1,mid+1,R);
    }
};