新乡网站建设公司,wordpress不显示,没有做网站能备案吗,网站空间域名费1. 题目
在一个 m*n 的二维字符串数组中输出二叉树#xff0c;并遵守以下规则#xff1a;
行数 m 应当等于给定二叉树的高度。列数 n 应当总是奇数。根节点的值#xff08;以字符串格式给出#xff09;应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分…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:vectorvectorstring printTree(TreeNode* root) {int height getHeight(root);//求高度int width (2(height-1))-1;//确定宽度vectorvectorstring ans(height,vectorstring (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(vectorvectorstring ans, TreeNode* root, int f, int L, int R){if(root NULL)return;int mid ((LR)1);//区间中点ans[f][mid] to_string(root-val);//f深度dfs(ans,root-left,f1,L,mid-1);//递归填充左右侧dfs(ans,root-right,f1,mid1,R);}
};
