PrintBinaryTree [source code]
public class PrintBinaryTree {
static
/******************************************************************************/
public class Solution {
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
int width = (int) Math.pow(2, height) - 1;
String[][] res = new String[height][width];
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
res[i][j] = "";
paint(root, res, 0, 0, width - 1);
List<List<String>> resLs = new ArrayList<>();
for (String[] row : res)
resLs.add(Arrays.asList(row));
return resLs;
}
public void paint(TreeNode root, String[][] matrix, int depth, int lo, int hi) {
if (depth == matrix.length || root == null)
return;
int mid = (lo + hi) / 2;
matrix[depth][mid] = root.val + "";
paint(root.left, matrix, depth + 1, lo, mid - 1);
paint(root.right, matrix, depth + 1, mid + 1, hi);
}
public int getHeight(TreeNode root) {
if (root == null)
return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}
/******************************************************************************/
public static void main(String[] args) {
PrintBinaryTree.Solution tester = new PrintBinaryTree.Solution();
}
}
感觉这个题目好像有点难度, 首先这个题目就不太好读懂, 5个rules刚开始没有看懂什么意思, 后来看出来是一个inductive的表达方式;
尝试用一个人逻辑去理解这个问题: 感觉这个问题用divide&conquer来解决的可能性比较大, 而且这个题目的关键应该是每一个root对应的column number的计算(也就是它对应的subtree需要的column number的计算);
稍微用人逻辑分析了一下例子, 感觉大概的思路是有了(刚开始看到这个题目就有点懵, 以为做不出来了, 结果花点时间还是有思路的). 下面就是想程序本身怎么写了, 尤其是你的recursion的返回值怎么设计, 等等的细节;
当然一个简单的做法就是直接返回当前的subtree对应的matrix, 不过感觉这个好像太慢了? 在想上一层的root level的组合是无法利用类似tree的指针操作之类的东西的, 所以组合的时候很可能会重新产生类似O(N)的cost, 这个最后搞下来整个的cost就很大了;
感觉用数学信息的方式, 给每一个matrix做一个数学信息上的总结, 作为返回值会比较好; 最后整个退出之后一个单独的pass来print;
本来的想法是column number这个size用一个recursion的思路来计算(2 * max_of_subtree_column + 1), 但是重新看了一下例子, 感觉好像并不需要? 直接根据height好像就可以计算?
吭哧吭哧写完了, 本来以为只有我一个人按照按照这个优化思路来写(这个思路避免频繁的array组合操作), 但是实际上最后的速度是10ms (50%), 好多人都是写出来这个解法;
另外关于这里的width的计算方式. 一开始还没有想到用2^N-1这个来计算, 就去百度了一下等比数列通项公式的解法, 正好找到这个题目对应的(a(n) = 2a(n-1) + 1). 不过真正要是临场没有这个时间(当着面试官的面去百度这些东西是有点姜), 就把1,2,3,4的全部都写出来, 当时归纳应该也是能够归纳出来的;
注意看2^N这个点, 下面有一个做法, 直接用shift来算, 可能比用math API来算好一些?
看了一下, 好像是editorial的原因, 这个题目虽然是新题目, 不过出来就有答案的:
public class Solution {
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
String[][] res = new String[height][(1 << height) - 1];
for(String[] arr:res)
Arrays.fill(arr,"");
List<List<String>> ans = new ArrayList<>();
fill(res, root, 0, 0, res[0].length);
for(String[] arr:res)
ans.add(Arrays.asList(arr));
return ans;
}
public void fill(String[][] res, TreeNode root, int i, int l, int r) {
if (root == null)
return;
res[i][(l + r) / 2] = "" + root.val;
fill(res, root.left, i + 1, l, (l + r) / 2);
fill(res, root.right, i + 1, (l + r + 1) / 2, r);
}
public int getHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}
这个好像就是submission的最优解;
写法跟我的几乎一模一样, 包括先做string matrix, 然后最后再转换成二维list(这样可以吃array的random access的速度的甜头)的小优化, 最后他们都是一样的;
也没什么丢人吧, 只能说损失了一个去discussion装逼的机会了. 但是直接写出来就跟最优解一模一样, 本身是一个值得高兴的事情;
editorial2是一个BFS的解法:
public class Solution {
class Params {
Params(TreeNode n, int ii, int ll, int rr) {
root = n;
i = ii;
l = ll;
r = rr;
}
TreeNode root;
int i, l, r;
}
public List < List < String >> printTree(TreeNode root) {
int height = getHeight(root);
System.out.println(height);
String[][] res = new String[height][(1 << height) - 1];
for (String[] arr: res)
Arrays.fill(arr, "");
List < List < String >> ans = new ArrayList < > ();
fill(res, root, 0, 0, res[0].length);
for (String[] arr: res)
ans.add(Arrays.asList(arr));
return ans;
}
public void fill(String[][] res, TreeNode root, int i, int l, int r) {
Queue < Params > queue = new LinkedList();
queue.add(new Params(root, 0, 0, res[0].length));
while (!queue.isEmpty()) {
Params p = queue.remove();
res[p.i][(p.l + p.r) / 2] = "" + p.root.val;
if (p.root.left != null)
queue.add(new Params(p.root.left, p.i + 1, p.l, (p.l + p.r) / 2));
if (p.root.right != null)
queue.add(new Params(p.root.right, p.i + 1, (p.l + p.r + 1) / 2, p.r));
}
}
public int getHeight(TreeNode root) {
Queue < TreeNode > queue = new LinkedList();
queue.add(root);
int height = 0;
while (!queue.isEmpty()) {
height++;
Queue < TreeNode > temp = new LinkedList();
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (node.left != null)
temp.add(node.left);
if (node.right != null)
temp.add(node.right);
}
queue = temp;
}
return height;
}
}
大概看了一下, 其实也是一个很trivial的翻译; 就是用BFS直接翻译recursion而已; 因为queue里面必须要有一个node的概念, 所以这里新定义了一个class, 用来封装每一个subproblem对应的信息; 反正看看也可以吧, 相对于普通的recursion翻译, 这个的难度可能要稍微大一点, 因为这个recursion问题里面的subproblem并不是直接就是你知道的比如TreeNode这样的东西, 而是要你自己去想, 这个subproblem需要的信息(参数表)是什么, 然后定义一个class来封装;
discussion里面一个略微笨点儿的解法:
public class Solution {
int height = 0, width = 0;
Map<String, String> map = new HashMap<>();
public List<List<String>> printTree(TreeNode root) {
List<List<String>> res = new ArrayList<List<String>>();
if (root == null) return res;
measure(root, 0);
mark(root, 0, 0, width - 1);
for (int i = 0; i < height; i++) {
List<String> row = new ArrayList<>();
for (int j = 0; j < width; j++) {
if (map.containsKey(i + "," + j)) {
row.add(map.get(i + "," + j));
}
else {
row.add("");
}
}
res.add(row);
}
return res;
}
private int measure(TreeNode root, int h) {
if (root == null) return 0;
height = Math.max(height, h + 1);
int w = Math.max(measure(root.left, h + 1), measure(root.right, h + 1)) * 2 + 1;
width = Math.max(width, w);
return w;
}
private void mark(TreeNode root, int y, int l, int r) {
if (root == null) return;
int x = (r + l) / 2;
map.put(y + "," + x, root.val + "");
mark(root.left, y + 1, l, x - 1);
mark(root.right, y + 1, x + 1, r);
}
}
解法本身因为漏掉了很多问题个性的insight, 所以最后显得有点笨, 不过还是值得看一看, 毕竟你真正自己面试的时候你也有可能漏掉insight, 学一学这种笨重的办法, 在走投无路的时候多一点办法; 包括他最后每一个row的信息summary的存储方式, 也是挺有意思: 用一个string来存, 存完了再来parse, 我当时425project的时候就干过类似的事情;
除了这些基本都是差不多的想法了, 这题没了;
Problem Description
Print a binary tree in an m*n 2D string array following these rules:
- The row number m should be equal to the height of the given binary tree.
- The column number n should always be an odd number.
- The root node's value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don't need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don't need to leave space for both of them.
- Each unused space should contain an empty string "".
- Print the subtrees following the same rules.
Example 1:
Input:
1
/
2
Output:
[["", "1", ""],
["2", "", ""]]
Example 2:
Input:
1
/ \
2 3
\
4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]
Example 3:
Input:
1
/ \
2 5
/
3
/
4
Output:
[["", "", "", "", "", "", "", "1", "", "", "", "", "", "", ""]
["", "", "", "2", "", "", "", "", "", "", "", "5", "", "", ""]
["", "3", "", "", "", "", "", "", "", "", "", "", "", "", ""]
["4", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]]
Note: The height of binary tree is in the range of [1, 10].
Difficulty:Medium
Total Accepted:1.2K
Total Submissions:2.4K
Contributor: fallcreek
Companies
poynt
Related Topics
tree