先通过先序遍历确定根,再通过中序遍历找到根并确定左右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, int> mpos;
// 传入一个前序遍历序列,一个中序遍历序列,返回一棵二叉树的根结点
TreeNode* dfs(vector<int>& po, int st0, int ed0,vector<int>& io, int st1, int ed1)
{
// st0,ed0先序起点和终点 st1,ed1中序起点和终点
// 递归边界
// 前序遍历只剩一个元素时,递归结束
if (ed0 == st0) return nullptr;
// 先序遍历找到根
int root = po[st0];
int pos = mpos[root]; // root 值在中序序列的下标
// 确定左子树的结点数
int lsize = pos - st1;
// 确定右子树的结点数
//int rsize = ed1 - pos - 1;//这里-1的原因是因为传入的ed的定义
TreeNode* node = new TreeNode(root);//答案
node->left = node->right = nullptr;
// 递归处理左子树
TreeNode* lt = dfs(
po, st0+1, st0+1+lsize,
io, st1, st1+lsize
);
// 递归处理右子树
TreeNode* rt = dfs(
po, st0+1+lsize, ed0,
io, pos+1, ed1
);
node->left = lt;
node->right = rt;
return node;
}
// po 前序遍历序列,io 中序遍历序列
TreeNode* buildTree(vector<int>& po, vector<int>& io) {
for (int i = 0; i < io.size(); i++)
mpos[io[i]] = i; // 中序遍历的下标
return dfs(po, 0, po.size(), io, 0, io.size());
}
};