重建二叉树
关键点:先序遍历中根节点一定在第一个,中序遍历根节点一定在中间位置。
根据上述特点我们就可以通过确定根节点来划分左右子树
同样的,对每个子树我们也递归的进行相同的操作
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]
通过preorder我们可以看出3是根节点
在通过inorder,可划分出左子树9,右子树15、20、7
具体到代码中,我们需要通过截取vector的方式实现
C++ 代码
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 终止条件,子树为空
if (preorder.size() == 0 || inorder.size() == 0) {
return nullptr;
}
// 获取根节点
int r_data = preorder[0];
int r_idx = 0;
for (int i=0; i<inorder.size(); i++) {
if (r_data == inorder[i])
r_idx = i;
}
// 创建根节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = r_data;
// 截取前序
vector<int> l_pre = getPart(preorder, 1, r_idx+1);
vector<int> r_pre = getPart(preorder, r_idx+1, preorder.size());
vector<int> l_in = getPart(inorder, 0, r_idx);
vector<int> r_in = getPart(inorder, r_idx+1, inorder.size());
// 递归创建子树
root->left = buildTree(l_pre, l_in);
root->right = buildTree(r_pre, r_in);
return root;
}
// 截取向量
vector<int> getPart(vector<int>& Arrs, int start, int end) {
vector<int> res;
if (start > end) return res;
vector<int>::const_iterator First = Arrs.begin() + start; // 找到第1个迭代器
vector<int>::const_iterator Second = Arrs.begin() + end; // 找到第2个迭代器
res.assign(First,Second);
return res;
}
};