1130 Infix Expression

题目大意

给出一棵树，让你输出中缀表达式。但是要符合括号格式。

---

思路解析

既然是中缀表达式妥妥的中序遍历没毛病。关键就是括号问题，仔细观察发现，括号是把左右子树分别括了起来，只有一个左右节点的不加括号；
比如：

这种情况输出结果是BAC,而不是（B）A（C）

二叉树的解题关键要把规模缩小，只着眼于三个节点的基本二叉树模型，通过递归解决问题，否则无从下手。所以有三种情况，分别是左右均有孩子；只有右孩子（因为是中缀树，不存在只有左孩子情况）；左右均没有孩子。然后分类解决即可。

---

示例代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct node{
public:
	string str;
	int left = -1, right = -1;
};
vector<node> vec;
vector<string> s1;
void func(int root) {
	if (vec[root].left != -1 && vec[root].right != -1) {//左右均有孩子
		s1.push_back("(");
		func(vec[root].left);
		s1.push_back(")");

		s1.push_back(vec[root].str);

		s1.push_back("(");
		func(vec[root].right);
		s1.push_back(")");
	}
	if (vec[root].left == -1 && vec[root].right != -1) {//只有右孩子
		s1.push_back(vec[root].str);
		s1.push_back("(");
		func(vec[root].right);
		s1.push_back(")");
	}
	if (vec[root].left == -1 && vec[root].right == -1) {//左右均没有孩子
		s1.push_back(vec[root].str);
	}	
}

int main() {
	int n, left, right;
	scanf("%d", &n);
	vec.resize(n + 1);
	vector<bool> isroot(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> vec[i].str;
		scanf("%d %d",  &left, &right);
		if (left != -1) {
			vec[i].left = left;
			isroot[left] = true;
		}
		if (right != -1) {
			vec[i].right = right;
			isroot[right] = true;
		}
	}
	int Root;
	for (Root = 1; Root <= n && isroot[Root]; Root++);
	func(Root);
	int pre = 0;
	vector<bool> isout(s1.size(),true);
	for (int i = 0; i < s1.size(); i++) {
		if (s1[i] == "(") {
			pre = i;
		}
		else if (s1[i] == ")") {
			if (i - pre == 2) {//中间只有一个元素的不加括号，要将括号剔除
				isout[pre] = false;
				isout[i] = false;
			}
		}
	}
	for (int i = 0; i < s1.size(); i++) {
		if (isout[i]) cout << s1[i];
	}
	return 0;
}