Construct Binary Tree from Preorder and Inorder Traversal算法复杂度？# JobHunting - 待字闺中
a*e
1 楼
下面这两个1.2.写法都是O（N^2)吧？为啥2说是O（N）呢？另外，看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0]);
return t;
}
else
return helper(preorder, inorder, 0, inorder.size()-1,0);
}
TreeNode *helper(vector &preorder, vector &inorder, int start,
int end, int rIdx)
{
if (start>end)
return NULL;
TreeNode *r = new TreeNode(preorder[rIdx]);
int mid=0;
for (int i=start; i<=end; i++)
{
if (inorder[i]==preorder[rIdx])
{
mid = i;
break;
}
}
r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1);
r->left = helper(preorder,inorder,start,mid-1,rIdx+1);
return r;
}
};
2.// LeetCode, Construct Binary Tree from Preorder and Inorder Traversal
// 递归，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
return buildTree(begin(preorder), end(preorder),
begin(inorder), end(inorder));
}
template
TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last,
InputIterator in_first, InputIterator in_last) {
if (pre_first == pre_last) return nullptr;
if (in_first == in_last) return nullptr;
auto root = new TreeNode(*pre_first);
auto inRootPos = find(in_first, in_last, *pre_first);
auto leftSize = distance(in_first, inRootPos);
root->left = buildTree(next(pre_first), next(pre_first,
leftSize + 1), in_first, next(in_first, leftSize));
root->right = buildTree(next(pre_first, leftSize + 1), pre_last,
next(inRootPos), in_last);
return root;
}
};
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0]);
return t;
}
else
return helper(preorder, inorder, 0, inorder.size()-1,0);
}
TreeNode *helper(vector
int end, int rIdx)
{
if (start>end)
return NULL;
TreeNode *r = new TreeNode(preorder[rIdx]);
int mid=0;
for (int i=start; i<=end; i++)
{
if (inorder[i]==preorder[rIdx])
{
mid = i;
break;
}
}
r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1);
r->left = helper(preorder,inorder,start,mid-1,rIdx+1);
return r;
}
};
2.// LeetCode, Construct Binary Tree from Preorder and Inorder Traversal
// 递归，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
TreeNode* buildTree(vector
return buildTree(begin(preorder), end(preorder),
begin(inorder), end(inorder));
}
template
TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last,
InputIterator in_first, InputIterator in_last) {
if (pre_first == pre_last) return nullptr;
if (in_first == in_last) return nullptr;
auto root = new TreeNode(*pre_first);
auto inRootPos = find(in_first, in_last, *pre_first);
auto leftSize = distance(in_first, inRootPos);
root->left = buildTree(next(pre_first), next(pre_first,
leftSize + 1), in_first, next(in_first, leftSize));
root->right = buildTree(next(pre_first, leftSize + 1), pre_last,
next(inRootPos), in_last);
return root;
}
};
