还不快抢沙发

添加新评论

在一个 m*n 的二维字符串数组中输出二叉树,并遵守以下规则: - 行数 m 应当等于给定二叉树的高度。 - 列数 n 应当总是奇数。 - 根节点的值(以字符串格式给出)应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分(左下部分和右下部分)。你应该将左子树输出在左下部分,右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空,你不需要为空的子树输出任何东西,但仍需要为另一个子树留出足够的空间。然而,如果两个子树都为空则不需要为它们留出任何空间。 - 每个未使用的空间应包含一个空的字符串""。 - 使用相同的规则输出子树。 示例1: ``` 输入: 1 / 2 输出: [["", "1", ""], ["2", "", ""]] ``` 示例2: ``` 输入: 1 / \ 2 3 \ 4 输出: [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]] ``` 示例3: ``` 输入: 1 / \ 2 5 / 3 / 4 输出: [["", "", "", "", "", "", "", "1", "", "", "", "", "", "", ""] ["", "", "", "2", "", "", "", "", "", "", "", "5", "", "", ""] ["", "3", "", "", "", "", "", "", "", "", "", "", "", "", ""] ["4", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]] ``` 解答: ```` vector printTree(TreeNode* root) { int m = depth(root); int n = (int)pow(2, m) - 1; vector row(n, ""); vector collection(m, row); printTreeRecur(root, collection, m, n / 2, 1); return collection; } void printTreeRecur(TreeNode* root, vector& collection, int m, int pos, int deepth) { if (!root) return; auto& row = collection.at(deepth - 1); row[pos] = to_string(root->val); deepth++; int step = (int)pow(2, m - deepth); printTreeRecur(root->left, collection, m, pos - step, deepth); printTreeRecur(root->right, collection, m, pos + step, deepth); } int depth(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return max(depth(root->left), depth(root->right)) + 1; } ````