https://leetcode.com/problems/print-binary-tree/
X. Level Order Traverse
https://leetcode.com/problems/print-binary-tree/discuss/106269/Java-Iterative-Level-Order-Traversal-with-Queue
http://www.cnblogs.com/grandyang/p/7489097.html
https://discuss.leetcode.com/topic/98381/java-recursive-solution
Print a binary tree in an m*n 2D string array following these rules:
- The row number
mshould be equal to the height of the given binary tree. - The column number
nshould 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].
https://leetcode.com/articles/print-binary-tree/X. Level Order Traverse
https://leetcode.com/problems/print-binary-tree/discuss/106269/Java-Iterative-Level-Order-Traversal-with-Queue
It could be fairly easy when we made our first observation on the problem. For the output matrix, the number of rows is height of the tree. What about the number of columns?
row = 1 => col = 1 = 2^1 - 1row = 2 => col = 3 = 2^2 - 1row = 3 => col = 7 = 2^3 - 1row = 4 => col = 15 = 2^4 - 1...row = m => col = 2^m - 1
This can be derived from the number of leaves of a full tree (i.e
2^(height - 1)) with spaces joined (i.e 2^(height - 1) - 1).
Then we can fill the node in level by level. Another observation is we always print a node at the center of its subtree index range. What I mean is for the left or right child of a
node, the subtree rooted at the child will use half of the indices of the node.rootis at the center ofleftandright, saymidroot.left(if not null) is at the center ofleftandmid - 1root.right(if not null) is at the center ofmid + 1andright
Then we can easily have our solution as we always keep track of the
left and right of the node.public class Solution {
public List<List<String>> printTree(TreeNode root) {
List<List<String>> res = new ArrayList<>();
if (root == null) {
return res;
}
int rows = getHeight(root);
int cols = (int)Math.pow(2, rows) - 1;
for (int i = 0; i < rows; i++) {
List<String> row = new ArrayList<>();
for (int j = 0; j < cols; j++) {
row.add("");
}
res.add(row);
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<int[]> indexQ = new LinkedList<>();
queue.offer(root);
indexQ.offer(new int[] { 0, cols - 1 });
int row = -1;
while (!queue.isEmpty()) {
row++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
int[] indices = indexQ.poll();
if (cur == null) {
continue;
}
int left = indices[0];
int right = indices[1];
int mid = left + (right - left) / 2;
res.get(row).set(mid, String.valueOf(cur.val));
queue.offer(cur.left);
queue.offer(cur.right);
indexQ.offer(new int[] { left, mid - 1 });
indexQ.offer(new int[] { mid + 1, right });
}
}
return res;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}http://www.cnblogs.com/grandyang/p/7489097.html
这道题给了我们一棵二叉树，让我们以数组的形式打印出来。数组每一行的宽度是二叉树的最底层数所能有的最多结点数，存在的结点需要填入到正确的位置上。那么这道题我们就应该首先要确定返回数组的宽度，由于宽度跟数组的深度有关，所以我们首先应该算出二叉树的最大深度，直接写一个子函数返回这个最大深度，从而计算出宽度。下面就是要遍历二叉树从而在数组中加入结点值。我们先来看第一行，由于根结点只有一个，所以第一行只需要插入一个数字，不管这一行多少个位置，我们都是在最中间的位置插入结点值。下面来看第二行，我们仔细观察可以发现，如果我们将这一行分为左右两部分，那么插入的位置还是在每一部分的中间位置，这样我们只要能确定分成的部分的左右边界位置，就知道插入结点的位置了，所以应该是使用分治法的思路。在递归函数中，如果当前node不存在或者当前深度超过了最大深度直接返回，否则就给中间位置赋值为结点值，然后对于左子结点，范围是左边界到中间位置，调用递归函数，注意当前深度加1；同理对于右子结点，范围是中间位置加1到右边界，调用递归函数，注意当前深度加1
https://discuss.leetcode.com/topic/98381/java-recursive-solution
public List<List<String>> printTree(TreeNode root) {
List<List<String>> res = new LinkedList<>();
int height = root == null ? 1 : getHeight(root);
int rows = height, columns = (int) (Math.pow(2, height) - 1);
List<String> row = new ArrayList<>();
for(int i = 0; i < columns; i++) row.add("");
for(int i = 0; i < rows; i++) res.add(new ArrayList<>(row));
populateRes(root, res, 0, rows, 0, columns - 1);
return res;
}
public void populateRes(TreeNode root, List<List<String>> res, int row, int totalRows, int i, int j) {
if (row == totalRows || root == null) return;
res.get(row).set((i+j)/2, Integer.toString(root.val));
populateRes(root.left, res, row+1, totalRows, i, (i+j)/2 - 1);
populateRes(root.right, res, row+1, totalRows, (i+j)/2+1, j);
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
First traversal measures height and width of final output. Second traversal record where should we put each node by using a HashMap.
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);
}