- 与树有关的问题第一时间尝试递归,分解子问题。
- 前序遍历的顺序是中左右,所以如果利用遍历结果建树,那么前序遍历数组的第一个数一定是根节点存储的树。
- 在中序遍历数组中找到这个根节点存储的数,因为中序遍历的顺序是左中右,所以中序遍历数组中该数左边的部分一定是根节点左子树存储的数,该数右边的部分一定是根节点右子树存储的数。
- 因为知道了中序遍历数组的左边界、右边界和根节点所在的下标,所以可以求出左子树、右子树的中序遍历数组长度,根据这些长度可以同样划分前序遍历数组。
- 利用划分出来的左右子树的前序遍历、中序遍历数组,对左子树和右子树递归建树,最后将指针赋值给根节点的左右子树指针,返回根节点即可。
class Solution {
public:
TreeNode* reConstructBinaryTree2(vector<int>& pre,vector<int>& vin, int pl, int pr, int vl, int vr) {
if (pl > pr) return nullptr;
if (pl == pr) return new TreeNode(pre[pl]);
TreeNode* res = new TreeNode(pre[pl]);
int vm = vl;
for (; vm <= vr; vm++) {
if (vin[vm] == pre[pl]) break;
}
res->left = reConstructBinaryTree2(pre, vin, pl + 1, pl + vm - vl, vl, vm - 1);
res->right = reConstructBinaryTree2(pre, vin, pl + vm - vl + 1, pr, vm + 1, vr);
return res;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return reConstructBinaryTree2(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
}
};