655 输出二叉树——Leetcode天天刷（2022.8.22）【DFS】

前言

刚打了今天的每日一题，难到是不难，算法上其实挺简单的。主要的问题是题目的描述出了一点问题，而且这种题目其实读起来有点像做阅读理解，不是很适合用来训练算法。

一开始很容易就想到了用两个DFS分别求高度和写答案，但是就想优化一下，看可不可以只遍历一次树，利用递归回溯来实现，但是却发现，树并不是一颗完全二叉树，所以还是需要遍历两次树才可以。

题目描述

题目传送门

感兴趣的可以点击传送门查看该题目作答。

先简单描述一下题目：

就是给你一颗二叉树的根节点，需要使用一个二维数组（矩阵）来表示这颗二叉树的 格式化布局。

构造格式化布局有以下规则：

这是官方对于构造规则的描述。

根据我对题目的理解，我发现了几个错误的地方并改为合理的理解:

1. 首先是行数，对于一颗二叉树，只要有根节点（不为空），那么它的高度至少是1，那么格式化的 矩阵 的 行数 应该是 高度height；

2. 其次是 列数，显然是2^(行数)次幂；

3. 其次对于左右子节点的列位置，我们记移动（左右）的距离为 mov，矩阵的行数为 row， 当前节点的位置是（r, c）,显然有如下公式
   $$mov=2^{row-r-2}$$

4. 矩阵的下标从0开始。

题目示例

输入：root = [1,2]
输出：
[["","1",""],
 ["2","",""]]
1
2
3
4

输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
 ["","2","","","","3",""],
 ["","","4","","","",""]]
1
2
3
4
5

提示

本地调试运行

输入格式

我们在本地调试运行的时候，官方的输入不一定适合。

所以我们需要对本地的输入做特殊化。

我们可以假定有多组输入，对每组输入，先输入一个整数n，表示输入得字符串数量，然后接下来的一行，输入n个字符串，字符串的内容要么是 纯数字，要么就是"null"。

输出格式

针对结果返回，我们需要输出格式化后的矩阵，我们规定按行输出，每一行中，如果字符串非空，则输出结果，否则输出空格，字符串之间也输出空格；每行之间用换行符'\n' 来分隔。

输入样例

2
1 2

5
1 2 3 null 4
1
2
3
4
5

输出样例

  1
2

      1
  2       3
    4
1
2
3
4
5
6

大家可以自己在本地上试一下。

解法——DFS

我们可以用两次DFS，第一次来求树的高度，然后根据高度来初始化答案矩阵，再来一次DFS，填充答案。

完整代码如下：

Code（C++）

#include
#include
#include
#include

typedef long long ll;
#define endl '\n'
using namespace std;
//Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Tree
{
public:
	TreeNode* root;

	// 构造函数利用BFS构造二叉树
	Tree(int n)
	{
		root = nullptr;
		if (!n)
		{
			return;
		}
		string s;
		--n;
		cin >> s;
		root = new TreeNode(stoi(s));			// 创建根节点
		queue<TreeNode*> que;			// 队列存储节点
		que.push(root);

		while (n && que.size())
		{
			TreeNode* node = que.front();
			que.pop();
			--n;
			cin >> s;
			if (s != "null")
			{
				node->left = new TreeNode(stoi(s));
				que.push(node->left);
			}
			if (!n)
			{
				break;
			}
			--n;
			cin >> s;
			if (s != "null")
			{
				node->right = new TreeNode(stoi(s));
				que.push(node->right);
			}
		}
	}

	// 写下析构函数，释放内存
	~Tree()
	{
		if (root)
		{
			dfs(root);
			TreeNode* temp = root;
			root = nullptr;
			delete temp;
		}
	}

	// DFS 递归释放内存
	void dfs(TreeNode* node)
	{
		if (!node)
		{
			return;
		}
		if (node->left)
		{
			dfs(node->left);
			TreeNode* temp = node->left;
			node->left = nullptr;
			delete temp;
		}
		if (node->right)
		{
			dfs(node->right);
			TreeNode* temp = node->right;
			node->right = nullptr;
			delete temp;
		}
	}
};

class Solution
{
public:
	// DFS
	// 先用DFS 计算树的高度
	// 再来一次DFS 将答案填充
	vector<vector<string>> printTree(TreeNode* root)
	{
		int height = comHeight(root);
		int row = height;						// 计算行数
		int col = pow(2, row) - 1 + 0.5;		// 计算列数，这里+0.5，是为了防止pow函数转int产生的精度丢失
		vector<vector<string>> ans(row, vector<string>(col, ""));		// 初始化矩阵
		int r = 0, c = (col - 1) / 2;			// 根节点的位置
		dfs(ans, root, r, c);					// DFS递归填充答案
		return ans;
	}

	// 求取以节点为根的树，求树的高度
	int comHeight(TreeNode* node)
	{
		if (!node)
		{
			return 0;
		}
		return max(comHeight(node->left), comHeight(node->right)) + 1;
	}

	// DFS递归填充答案
	void dfs(vector<vector<string>>& ans, TreeNode* node, int r, int c)
	{
		if (!node)
		{
			return;
		}
		// 填充答案
		ans[r][c] = to_string(node->val);
		int mi = ans.size() - 1 - r - 1;		// 计算2的幂次
		// 跳过幂次小于0的情况
		if (mi < 0)
		{
			return;
		}
		int mov = pow(2, mi) + 0.5;
		int c1 = c - mov;			// 左子节点的列位置
		if (c1 >= 0)
		{
			dfs(ans, node->left, r + 1, c1);		// 递归填充
		}
		int c2 = c + mov;			// 右子节点的列位置
		if (c2 < ans[0].size())
		{
			dfs(ans, node->right, r + 1, c2);
		}
	}
};

// 用来输出一下结果
void show(vector<vector<string>>& ans)
{
	int m = ans.size();
	int n = ans[0].size();
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (j)
			{
				cout << ' ';
			}
			if (ans[i][j] != "")
			{
				cout << ans[i][j];
			}
			else
			{
				cout << ' ';
			}
		}
		cout << endl;
	}
}


int main()
{
	int n;
	Tree* tree;
	Solution* sol = new Solution();
	while (~scanf("%d", &n))
	{
		tree = new Tree(n);
		TreeNode* root = tree->root;
		auto ans = sol->printTree(root);
		show(ans);
		delete tree;
	}
	delete sol;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

解法效率

时间复杂度 O(n)， n为树的节点数量。

空间复杂度O(r*c)， r，c分别为矩阵的行列数。

后话

冲冲冲！