0%

输出二叉树

发表于 分类于 ， Disqus：

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：

  • 行数 m 应当等于给定二叉树的高度。
  • 列数 n 应当总是奇数。
  • 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
  • 每个未使用的空间应包含一个空的字符串””。
  • 使用相同的规则输出子树。
    示例1：
    1
    2
    3
    4
    5
    6
    7
    输入:
         1
        /
       2
    输出:
    [["", "1", ""],
     ["2", "", ""]]
    示例2：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    输入:
         1
        / \
       2   3
        \
         4
    输出:
    [["", "", "", "1", "", "", ""],
     ["", "2", "", "", "", "3", ""],
     ["", "", "4", "", "", "", ""]]
    示例3：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    输入:
          1
         / \
        2   5
       / 
      3 
     / 
    4 
    输出:
    [["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
     ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
     ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
     ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<string>> printTree(TreeNode* root) {
		int m = depth(root);
		int n = (int)pow(2, m) - 1;
		vector<string> row(n, "");
		vector<vector<string>> collection(m, row);
		printTreeRecur(root, collection, m, n / 2, 1);
		return collection;
	}

	void printTreeRecur(TreeNode* root, vector<vector<string>>& 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;
	}