655. Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

1. The row number m should be equal to the height of the given binary tree.
2. The column number n should always be an odd number.
3. 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.
4. Each unused space should contain an empty string "".
5. 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].

---

很有意思的一个题，考察了二叉树的多个知识点。

给定一棵二叉树，要求逐层打印出每一层节点的值，而且子节点的位置要在父节点位置的下一层的左边。根据样例可以看到，打印出来的二维数组，如果把每层节点连起来的话，就是原来二叉树的形状。

观察样例可以发现这样一些规律：二叉树的高度就是二维数组的行数；假设高度为h，则二维数组的列数就是$2^h-1$。所以，首先根据LeetCode Maximum Depth of Binary Tree求出二叉树的高度，然后构造好目标大小的二维数组。

接着就是根据二叉树填充数组了。树的题目一般都是用递归来解决，这题也不例外。我们设计一个work函数，每次传入当前需要填充的树节点，二维数组的行号（层数），该节点所在的列数范围。当填充好这个节点后，递归的填充其左节点和右节点，层数加一，同时更新列数范围。

完整代码如下：

class Solution {
public:
	int height(TreeNode* root) {
		if (root == NULL)return 0;
		if (root->left == NULL && root->right == NULL)return 1;
		int lh = height(root->left), rh = height(root->right);
		return (lh > rh ? lh : rh) + 1;
	}
	void work(TreeNode* root, vector<vector<string>>& strTree,int layer,int left,int right) {
		if (root == NULL)return;
		int mid = (left + right) / 2;
		strTree[layer][mid] = to_string(root->val);
		work(root->left, strTree, layer + 1, left, mid - 1);
		work(root->right, strTree, layer + 1, mid + 1, right);
	}
	vector<vector<string>> printTree(TreeNode* root) {
		int h = height(root);
		vector<vector<string>> strTree(h, vector<string>((1 << h) - 1, ""));
		work(root, strTree, 0, 0, strTree[0].size() - 1);
		return strTree;
	}
};

本代码提交AC，用时0MS，性能还是不错的。