题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
通过前序遍历和中序遍历即可确定一颗树，树的题目直接思考递归，因此对此题，首先可发现前序遍历的第一个元素为根节点，则在中序遍历中找到该根节点即可将该树的左右子树找出。因此可递归，第一次输入两个完整数组，将pre数组的p[0]变为树节点，则左接(cutpre,cutvin)，右接(cutpre,cutvin)，即传入的新数组为裁剪过的分别只剩左子树和右子树的数组。时间复杂度遍历了数组所以时间复杂度为O(n),裁剪和找下标均为O(n)，所以总的时间复杂度为O(n),空间复杂度也为O(n).
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
if (pre.empty() && vin.empty()) {
return NULL;
}
TreeNode* root = dfs(pre, vin);
return root;
}
TreeNode* dfs(vector<int> pre, vector<int> vin) {
if (pre.empty()&&vin.empty()) {
return NULL;
}
TreeNode* root = new TreeNode(pre[0]);
int index=find(vin, root->val);
root->left = dfs(cut(pre,1,index), cut(vin,0,index-1));
root->right = dfs(cut(pre,index+1,pre.size()-1), cut(vin,index+1,vin.size()-1));
return root;
}
//查询下标
int find(vector<int> a, int b) {
for (int i = 0; i < a.size(); i++) {
if (a[i] == b) {
return i;
}
}
return 0;
}
//截取vector片段
vector<int> cut(vector<int> res, int i, int j) {
vector<int> ans;
if (i > j) {
return ans;
}
for (int k = i; k <= j; k++) {
ans.push_back(res[k]);
}
return ans;
}
};
查看8道真题和解析
上海华为技术有限公司主管面11人在聊