655.输出二叉树
虽然我们可以知道这一题的大致思想可以利用 深度优先搜索，但还是有很大细节。
题目中有这样一段：
- 树的高度为
height，矩阵的行数m应该等于height + 1。- 矩阵的列数
n应该等于2 的（height+1）次方 - 1
不难看出，行数应表示 一颗满二叉树的层数，而列数应表示 满二叉树的结点个数 .
而题目中 的高度显然不是 从根节点开始计算，也即为其子树的高度。
比如一颗高度为 3（包括根节点）的满二叉树，的结点个数为 7.而题目中根据其公式：
2 ^ (height + 1) -1 = 7解得height = 2. 也就是指其子树的高度。
搞清楚这一点就好办很多。
解题思路：
1. 首先我们需要获取高度，根据高度来设置字符串矩阵的 行 与 列
2. 接着 利用循环将这个字符串矩阵全部用 “” 进行填充。
3. 根据结点是否存在，再利用set()方法将结点的val值替换掉 “” 。
代码 如下：
class Solution {
// private int he = 0;
public List<List> printTree(TreeNode root) {
int h = getHeight(root);
int m = h ;//行数
int n = (1 << (h)) – 1; //列数
List<List> res = new ArrayList<List>();
for(int i = 0; i < m; i++){ //利用循环 首先将字符串矩阵全部用 "" 进行填充
List row = new ArrayList();
for(int j = 0; j < n; j++){
row.add(“”);
}
res.add(row);
}
dfs(res,root,0,(n-1)/2,h-1); // 这里传入 h-1 表示从它的子树开始计算（与题目相对应）
return res;
}
public int getHeight(TreeNode root) { //该方法获取的高度为从根节点开始的高度。
return
Math.max(root.left == null ? 0 : getHeight(root.left) ,
root.right == null ? 0 : getHeight(root.right))+1;
}
//
public void dfs(List<List> res, TreeNode root, int r, int c, int h){
res.get(r).set(c,Integer.toString(root.val));
if(root.left != null) {
dfs(res,root.left,r+1,c-(1<<h-r-1),h);
}
if(root.right != null){
dfs(res,root.right,r+1,c+(1<<h-r-1),h);
}
}
}
特别说明，我们每次计算父节点的位置 比如根节点的位置为 （n-1）/2.
而在dfs() 方法中 第一个递归里的参数 c-(1<<h-r-1) 表示父节点的左子节点在一维字符串列表的下标。（题目中其实已经给了，可以试着带一个具体的参数进去即可理解）