这题说的是根据前序遍历数组和中序遍历数组来重建二叉树。我们知道前序遍历数组的第一个元素一定是根节点，在中序遍历数组中，根节点前面的都是根节点左子树上的节点，根节点后面的都是根节点右子树上的节点。左右两棵子树我们可以使用递归的方式继续创建。
我们首先使用前序数组的第一个元素创建根节点，然后查询该节点在中序遍历数组中的位置，把中序数组分成两部分，一部分是根节点左子树的节点，一部分是根节点右子树的节点。为了方便查询，我们可以提前把中序数组存储到 map 中。
比如前序数组是：{1,2,4,7,3,5,6,8}，中序数组是：{4,7,2,1,5,3,8,6}
那么 1 就是根节点，中序数组中 1 左边的 {4,7,2} 就是根节点左子树上的所有节点， 1 的右边 {5,3,8,6} 就是根节点右子树上的所有节点，如下图所示。
public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
// 为了方便后续进行查找，先把中序数组的所有值存储到map中
Map<Integer, Integer> mp = new HashMap<>();
int n = vinOrder.length;
for (int i = 0; i < n; i++)
mp.put(vinOrder[i], i);
return build(preOrder, mp, 0, 0, n - 1);
}
/**
* @param preorder 前序遍历的数组
* @param mp map，存储的是中序遍历的数组
* @param preStart 前序遍历数组中的第一个元素下标
* @param inStart 中序遍历数组的起始位置
* @param inEnd 中序遍历数组的结束位置
* @return
*/
private TreeNode build(int[] preorder, Map<Integer, Integer> mp,
int preStart, int inStart, int inEnd) {
if (inStart > inEnd)// 表示数组被访问完了。
return null;
// 使用前序数组的第一个元素创建node节点
TreeNode node = new TreeNode(preorder[preStart]);
// 查找node节点在中序数组中位置
int index = mp.get(node.val);
int leftCnt = index - inStart;// node节点左子树的所有节点个数。
// 前序数组区间划分：
// [preStart, preStart]根节点
// [preStart + 1, preStart + leftCount]左子树
// [preStart + leftCount + 1, ……]右子树
// 中序数组区间划分：
// [inStart, index - 1]左子树
// [index, index]根节点
// [index + 1, inEnd]右子树
node.left = build(preorder, mp, preStart + 1, inStart, index - 1);// 递归创建左子树和右子树
node.right = build(preorder, mp, preStart + leftCnt + 1, index + 1, inEnd);
return node;
}
public:
TreeNode *reConstructBinaryTree(vector<int> &preOrder, vector<int> &vinOrder) {
// 为了方便后续进行查找，先把中序数组的所有值存储到map中
unordered_map<int, int> mp;
int n = vinOrder.size();
for (int i = 0; i < n; i++)
mp[vinOrder[i]] = i;
return build(preOrder, mp, 0, 0, n - 1);
}
/**
* @param preorder 前序遍历的数组
* @param mp map，存储的是中序遍历的数组
* @param preStart 前序遍历数组中的第一个元素下标
* @param inStart 中序遍历数组的起始位置
* @param inEnd 中序遍历数组的结束位置
* @return
*/
TreeNode *build(vector<int> &preorder, unordered_map<int, int> &mp,
int preStart, int inStart, int inEnd) {
if (inStart > inEnd)// 表示数组被访问完了。
return nullptr;
// 使用前序数组的第一个元素创建node节点
auto *node = new TreeNode(preorder[preStart]);
// 查找node节点在中序数组中位置
int index = mp[node->val];
int leftCnt = index - inStart;// node节点左子树的所有节点个数。
// 前序数组区间划分：
// [preStart, preStart]根节点
// [preStart + 1, preStart + leftCount]左子树
// [preStart + leftCount + 1, ……]右子树
// 中序数组区间划分：
// [inStart, index - 1]左子树
// [index, index]根节点
// [index + 1, inEnd]右子树
node->left = build(preorder, mp, preStart + 1, inStart, index - 1);// 递归创建左子树和右子树
node->right = build(preorder, mp, preStart + leftCnt + 1, index + 1, inEnd);
return node;
}
京公网安备 11010502036488号