anonymous
BAN USERThis is simply not a complete description of the question. The short answer is that there is no way.
Think about two trees:
4
3 nullptr
3
nullptr 4
Both of the trees have exactly the same pre-order traversal, which is 3 4, if nullptr is not taken into account.
The leaf node can be either 3 or 4 depending on the tree, whose information is lost during pre-order traversal.
If we take nullptr into account, this is a simple question. Any time we find two nullptrs after a node, we count it as a leaf. But I guess it is not what the interviewer wanted.
int countSubSet( const vector<int>& nums , int target ){
int total = 0;
sort( nums.begin() , nums.end() );
for( int i = 0 ; i < nums.size(); ++i ){
auto it = lower_bound( nums.begin() , nums.end() , target - nums[i] );
if( it - nums.begin() > i )
continue;
int j = ( nums[i] + *it == target ) ? it - nums.begin() - 1 : it - nums.begin();
while( j >= 0 ){
total += pow( 2 , max( 0 , i - j - 1 ) );
--j;
}
}
return total;
}
bool combinationSum( const vector<int>& nums , int target ){
const int n = nums.size();
if( n == 0 )
return false;
vector<bool> dp( n + 1 , false );
dp[0] = true;
for( auto num : nums ){
for( int i = num ; i <= target ; ++i )
dp[i] = dp[i] | dp[i-num];
}
return dp.back();
}
- anonymous March 25, 2017