不务正业之pat解题：1130. Infix Expression (25)

[yooocen]

两个问题：一个是怎么样获取根结点，其实很简单，没有父节点的节点就是根节点。表达式是指除了根结点以外的子树，一颗子树是一个表达式的前提是它的右节点一定不为空

#include <iostream>
#include <vector>
using namespace std;
struct node {
    string val;
    int left, right;
};
vector<node> v;
int n , root;

string dfs(int index ){
    if (index==-1) {
        return "";
    }
    if(v[index].right!=-1){
        if(index!=root){
            return "("+ dfs(v[index].left)+v[index].val+dfs(v[index].right)+")";
        }else{
            return dfs(v[index].left)+v[index].val+dfs(v[index].right);
        }
    }
    return v[index].val;
}

int main() {
    cin >> n;
    v.resize(n + 1);
    vector<bool> visit(n+1,false);
    //找到根节点
    for(int i = 1; i< n+1 ; i++){
        cin >> v[i].val;
        cin >> v[i].left;
        cin >> v[i].right;
        if(v[i].left!=-1)
        visit[v[i].left] = true;
        if(v[i].right!=-1)
        visit[v[i].right] = true;
    }
    for(int i = 1 ; i <= n ;i++){
        if(!visit[i]){
            root = i;
            break;
        }
    }
    cout<<dfs(root);
    return 0;
}