105 从前序与中序遍历构造二叉树
直接做法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
if(preorderStart > preorderEnd || inorderStart > inorderEnd)
return nullptr;
auto it = find(inorder.begin()+inorderStart, inorder.begin()+inorderEnd + 1, preorder[preorderStart]);
int pos = distance(inorder.begin(), it);
int leftSubTreeNum = pos - inorderStart;
TreeNode* root = new TreeNode(inorder[pos]);
root->left = myBuildTree(preorder,inorder,preorderStart + 1, preorderStart + leftSubTreeNum, inorderStart, pos - 1);
root->right = myBuildTree(preorder,inorder, preorderStart + leftSubTreeNum + 1, preorderEnd, pos + 1, inorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return myBuildTree(preorder, inorder,0,preorder.size() - 1, 0, inorder.size() - 1);
}
};
直接做法的优化
find的时间复杂度为\(O(n)\),可以进一步优化为哈希表查询,时间复杂度改为\(O(1)\)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
if(preorderStart > preorderEnd || inorderStart > inorderEnd)
return nullptr;
int pos = hashMap[preorder[preorderStart]];
int leftSubTreeNum = pos - inorderStart;
TreeNode* root = new TreeNode(inorder[pos]);
root->left = myBuildTree(preorder,inorder,preorderStart + 1, preorderStart + leftSubTreeNum, inorderStart, pos - 1);
root->right = myBuildTree(preorder,inorder, preorderStart + leftSubTreeNum + 1, preorderEnd, pos + 1, inorderEnd);
return root;
}
public:
unordered_map<int, int> hashMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0; i < inorder.size(); i++){
hashMap[inorder[i]] = i;
}
return myBuildTree(preorder, inorder,0,preorder.size() - 1, 0, inorder.size() - 1);
}
};
时间复杂度:O(n),其中 n 是树中的节点个数。
空间复杂度:O(n),除去返回的答案需要的 O(n) 空间之外,我们还需要使用 O(n) 的空间存储哈希映射,以及 O(h)(其中 h 是树的高度)的空间表示递归时栈空间。这里 h<n,所以总空间复杂度为 O(n)。
迭代
待补充