@Don: You certainly can get by with only one workspace of size O(n). One
side of the partitioning is done in-place, with the other side accumulated
in the workspace and then copied back into the input array. That's a lot
better than the O(n^2) worst case workspace required by your original
It definitely complicates things. I think that I would replaced the vector
parameters with pointers to the beginning and end of each array. The
partition is tricky because you need to make sure that both subtrees end up
in the same order they started in, which is difficult because most
You don't need to take vector for this you can have input in array also.
You just need to check the elements in each partition .
On 12-Jul-2013 8:27 PM, Don dondod...@gmail.com wrote:
Can anyone modify this solution so that it does not duplicate the memory
at each level of recursion?
(Here is
Can anyone modify this solution so that it does not duplicate the memory at
each level of recursion?
(Here is my solution with the fix mentioned above)
typedef std::vectorint btree;
bool sameBstFormed(btree t1, btree t2)
{
bool result;
if (t1.size() != t2.size()) result = false;
else
The trees would be the same if
1. The root is the same
2. The left and right subtrees are both the same
bool sameBstFormed(intVector t1, intVector t2)
{
if (t1.size() != t2.size()) return false; // Trees with different
number of nodes can't be the same
if (t1.size() == 0) return
Amazing solution Don, thank you :) You missed a small check in the code:
if(t1[0] != t2[0]) return 0;
On Tue, Jul 9, 2013 at 11:27 PM, Don dondod...@gmail.com wrote:
The trees would be the same if
1. The root is the same
2. The left and right subtrees are both the same
bool
Yes, you are right. Good catch.
On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:
Amazing solution Don, thank you :) You missed a small check in the code:
if(t1[0] != t2[0]) return 0;
On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com javascript:wrote:
The trees
