算法1
(递归) $O(n)$
1、用unorder_map
存储inorder
中每个元素的下标
2、每层递归,根据preorder
的第一个值确定这一层的根节点
3、根据unorder_map
确定根节点在inorder
中下标
4、通过根节点在inorder
中的下标,以及这层递归inorder
左右边界的下标,确定左右子树个数
5、根据左右子树的个数划分preorder
,进行下一层递归
时间复杂度
共有n个根节点,时间复杂度是$O(n)$
C++ 代码
class Solution {
public:
unordered_map<int, int> hash;
vector<int> preorder, inorder;
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
preorder = _preorder, inorder = _inorder;
for(int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;//构建hash表
return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode *dfs(int pl, int pr, int il, int ir)
{
if(pl > pr) return nullptr;
auto root = new TreeNode(preorder[pl]);//确定根节点
int k = hash[root->val];//找到根节点在inorder中的坐标
//左子树在preorder中的范围[pl + 1, pl + 1 + (k - il + 1)]
root->left = dfs(pl + 1, pl+ k - il, il, k - 1);
root->right = dfs(pl + k - il + 1, pr, k + 1, ir);
return root;
}
};