首页 程序设计 图与树

# 怎么样的情况可以构建树呢？

  • 中序 ++ 前序
  • 中序 ++ 后序
  • 中序 ++ 层序
    必须要有中序，其他随便搭

# 示例代码

# 中序 + 前序

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//             根位置  左      右
Node *build(int pos, int l, int r) {
	if (l > r)
		return null;
	Node *root = new Node();
	
	root->val = pre[pos];
	int idx = mp[pre[pos]], len = idx - l;
	
	root->left = build(pos + 1, l, idx - 1);
	root->right = build(pos + idx + 1, idx + 1, r);
	
	return root; 
}

# 中序 + 后序

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//             根位置  左      右        
Node *build(int pos, int l, int r) {
	if (l > r)
		return null;
	
	Node *root = new Node();
	root->val = lst[pos];
	int idx = mp[lst[pos]], len = r - idx;
	
	root->right = build(pos - 1, idx + 1, r);
	root->left = build(pos - len - 1, l, idx - 1);
	
	return root;
}

# 中序 + 层序

C++
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
int n, mid[N], lev[N];
map<int, int> mp;

Node* build(int l, int r, const vector<int>& level) {
	if (l > r)
		return null;

	Node* root = new Node();
	root->val = level[0];
	int pos = mp[root->val];

	vector<int> leftLev, rightLev;
	for (int i = 1; i < level.size(); i++) {
		int p = mp[level[i]];

		if (p < pos)
			leftLev.push_back(level[i]);
		else
			rightLev.push_back(level[i]);
	}

	root->left = build(l, pos - 1, leftLev);
	root->right = build(pos + 1, r, rightLev);
	return root;
}