[BST的构建][C++实现]

今天前面碰到一题，判定给定的BST是否是合法的，因为BST性质，LDR遍历递增，根据这个来判定即可。但是碰到给定自行构建BST的时候，给定的输入是这样的：

5 1

5 2 3

1 0 0

3 4 5

4 0 0

6 0 0 

什么意思呢，第一行为n和root，分别代表总共n个节点，并且root节点为序号root的节点。

之后每一行输入的是三个数，分别为val，left_idx，right_idx来进行链接关系，如果碰到idx=0的，说明子节点为空

想了蛮久到底怎么样去构建这棵树比较好，感觉还是总结一下吧

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{ //定义树节点
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};

void LDR(TreeNode* root,vector<int>& res){
    if(!root){
        return;
    }
    LDR(root->left,res);
    res.push_back(root->val);
    LDR(root->right,res);
    return;
}
int main(){
    int n,root_idx; //总共n个点
    cin>>n>>root_idx;
    int val,left_idx,right_idx; //一行中的三个信息
    vector<pair<int,pair<int,int>>> vec; //存每行的信息
    vector<TreeNode*> node; //存所有的node节点
    for(int i=0;i<n;++i){
        cin>>val>>left_idx>>right_idx;
        node.push_back(new TreeNode(val)); //当前节点进行创建，之后进行相连即可
        vec.push_back({val,{left_idx-1,right_idx-1}}); //记住，给定的和实际的有差值1
    }
    TreeNode* root=node[0]; //这是最后的根节点
    for(int i=0;i<vec.size();++i){
        if(vec[i].second.first>0){ //如果左子节点是存在的，进行相连，之前一直判断这里错误了，因为1的差值，此时会出现-1，因此要判断>0
            node[i]->left=node[vec[i].second.first];
        }
        if(vec[i].second.second>0){
            node[i]->right=node[vec[i].second.second];
        }
    }
    //到目前为止已经创建成功，check一下,LDR观察一下
    vector<int> res;
    LDR(root,res);
    cout<<"The LDR sequence is: ";
    for(int i=0;i<res.size();++i){
        cout<<res[i]<<" ";
    }
    system("pause");
    return 0;
}

运行截图如下：