https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

c++

1---判断是否为空，边界条件
2---找到root的位置

---vin左: [0-------root_index-1]
---pre左：[1--------root_index]

---vin右：[root_index+1------end]
---pre右：[root_index+1------end]

(pre左，vin左) (pre右，vin右)

```class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (vin.size() == 0){
return NULL;
}
TreeNode* root = new TreeNode(pre[0]); // defined  tree root
vector<int> pre_left, pre_right, vin_left, vin_right; // difine and record tree infor
// find root index in vin
int root_ind=0;
for(int ind=0; ind<vin.size(); ind++){
if (vin[ind] == pre[0]){
root_ind=ind;
break;
}
}
// update right lefte
for(int i=0; i<root_ind; i++){
vin_left.push_back(vin[i]);
pre_left.push_back(pre[i+1]);//the first is root, need plus 1
}
for(int i=root_ind+1; i<vin.size(); i++){
vin_right.push_back(vin[i]);
pre_right.push_back(pre[i]);
}
// 递归
root->left = reConstructBinaryTree(pre_left, vin_left);
root->right = reConstructBinaryTree(pre_right, vin_right);
return root;
}
};```

01-09 08:45

2022-12-29 12:43

02-02 11:38

2022-12-19 18:55

01-16 09:59

2022-12-07 19:38

2022-12-09 14:30