655. Print Binary Tree

这是刚才的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