a***e
发帖数: 413 | 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;
}
}; | f*******w
发帖数: 1243 | 2 应该都是n^2吧。这两个方法好像没有任何区别啊。
除非find()还有什么特别的技巧？不过在没排序的vector里面查找肯定是O(n)了。
如果数组没重复的话，可以先把inorder存在hash里，key是数组里面的值，value是
index。这样能做到O(n) in time. | a***e
发帖数: 413 | 3 多谢大牛，我觉得它们都是O（N^2），但看2说自己是O（N）又不确定了。
下面这种解法应该怎么分析复杂度呢？我觉得是O（N）但还是不确定。
class Solution {
public:
TreeNode *buildTree(vector &pre, vector &in) {
int i=0,j=0;
TreeNode *root=new TreeNode(0x80000000);
TreeNode *pp=NULL,*ptr=root;
stack sn;sn.push(root);
while (j
if (sn.top()->val==in[j]) {
pp=sn.top();
sn.pop();
j++;
} else if (pp) {
ptr=new TreeNode(pre[i]);
pp->right=ptr;pp=NULL;
sn.push(ptr);
i++;
} else {
ptr=new TreeNode(pre[i]);
sn.top()->left=ptr;
sn.push(ptr);
i++;
}
}
ptr=root->left;delete root;
return ptr;
}
}; | b******g
发帖数: 3616 | 4 这个应该是O(N)了，除了第一个元素外，其他每个元素进出栈一次，而且i,j各扫描pre
,in一次。
这个算法很牛啊，虽然follow了个简单的例子觉得算法应该是对的，但还没有完全理解
是什么原理。请高手解释！
【在 a***e 的大作中提到】
: 多谢大牛，我觉得它们都是O（N^2），但看2说自己是O（N）又不确定了。
: 下面这种解法应该怎么分析复杂度呢？我觉得是O（N）但还是不确定。
: class Solution {
: public:
: TreeNode *buildTree(vector &pre, vector &in) {
: int i=0,j=0;
: TreeNode *root=new TreeNode(0x80000000);
: TreeNode *pp=NULL,*ptr=root;
: stack sn;sn.push(root);
: while (j
| a***e
发帖数: 413 | 5 这个是在leetcode的讨论中一个叫dtx0的同学贴的。
gpraveenkumar的idea和他/她的几乎一样
The idea is as follows: 程序中没用flag，而是用pp这个指针
1) Keep pushing the nodes from the preorder into a stack (and keep making
the tree by adding nodes to the left of the previous node) until the top of
the stack matches the inorder.
2) At this point, pop the top of the stack until the top does not equal
inorder (keep a flag to note that you have made a pop).
3) Repeat 1 and 2 until preorder is empty. The key point is that whenever
the flag is set, insert a node to the right and reset the flag.
我仔细看了，觉得算法很巧妙。
我的理解是根据preorder inorder的基本原理，
1）能够保证左子树都入栈
2）3）中pop出来的node的左子树都在栈下面压着，所以在preorder里面的下一个肯定
是right child。
不知道怎么正式的证明，期待大牛们的讨论。 |
|
