题目大意：
输出二叉树
在一个 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] 中。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=655
解题思路分析：
本题首先要确定出最后要打印的二维数组的高和宽，二维数组的高就是二叉树的高度，宽则是二叉树在满节点状态下的总节点个数，二叉树总节点个数的计算方法是2的m次方减一，其中m为二叉树高度。求二叉树高度可以使用bfs。
在确定了高和宽之后，我们再使用dfs描画每一条路径。dfs方法需要三个重要参数，当前行，当前列的左端和右端范围。dfs起始点为二叉树顶点，顶点一定在首行的中间位置，因此，此时当前行为0，当前列的范围是[left, n-1]，其中left为0，n为总列数。当前列的范围中点mid即是顶点的所在位置。描画完顶点之后，如果其存在左子节点，那么将左节点递归至子问题，此时行数加一，列的范围变为[left, mid-1]，同理，右子节点的范围应该是[mid+1, right]。循环此步骤直到描画完所有节点为止。
个人感觉这是一道同时练习bfs和dfs很好的题目。
实现代码：
public List<List<String>> printTree(TreeNode root) {
int height = bfs(root); // 计算二叉树高度
int width = (int)Math.pow(2, height) - 1; // 宽度
// 返回结果
List<List<String>> res = new ArrayList<>();
for(int i=0;i<height;i++){
List<String> list = new ArrayList<>();
for(int j=0;j<width;j++){
list.add("");
}
res.add(list);
}
// 递归描画每个节点
dfs(root, 0, 0,width-1,res);
return res;
}
int bfs(TreeNode root){
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int height=0;
while(q.size()>0){
int size=q.size();
while(size>0){
size--;
TreeNode n = q.poll();
if(n.left!=null) q.offer(n.left);
if(n.right!=null) q.offer(n.right);
}
height++;
}
return height;
}
void dfs(TreeNode root, int r, int left, int right, List<List<String>> res){
int mid = (left+right)/2;
res.get(r).set(mid, String.valueOf(root.val));
if(root.left!=null){
dfs(root.left, r+1, left, mid-1,res);
}
if(root.right!=null){
dfs(root.right, r+1, mid+1, right,res);
}
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 99.91% of Java online submissions for Print Binary Tree.
Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Print Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-655-print-binary-tree-解题思路分析/