这是刚才的Contest的第三题。这题我的思路是，
第一步：算出树的深度
第二步：BFS遍历Tree，把NULL节点也存下来
第三步：找出一个关于深度的公式，把第二步保存的值构造成结果
其中第二步，我一直想写一个能够构造leetcode的那种serialization的函数。。这题的关键好像就是那个。
然后我就不想想了，怠惰。后面更吧。好懒啊。
--
发现之前这个思路不太可行，第二步不太会。
看了下答案，就是dfs做层序遍历的那种方法，在每层get相应的list把值加进去。
public class Solution {
private int getHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
private void dfs(List<List<String>> res, TreeNode root, int left, int right, int level) {
//不需要也不能有left>=right的条件
if (root == null)
return;
int mid = left + (right - left) / 2;
res.get(level).set(mid, String.valueOf(root.val));
dfs(res, root.left, left, mid, level + 1);
dfs(res, root.right, mid + 1, right, level + 1);
}
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
//左移运算符的优先级低，要加括号。
int width = (1 << height) - 1;
List<List<String>> res = new ArrayList<>();
for (int i = 0; i < height; i++) {
List<String> item = new ArrayList<>();
for (int j = 0; j < width; j++) {
item.add("");
}
res.add(new ArrayList<String>(item));
}
dfs(res, root, 0, width - 1, 0);
return res;
}
}
ref:
https://discuss.leetcode.com/topic/98513/simple-java-solution-easy-for-sure
