服务器win7网站建设,营销型企业网站的功能有哪些,自己怎么设计公司的logo,Wordpress5主题破解版题目链接#xff1a;0, 1, 2, Tree!
本道题目其实就是一道贪心的题目#xff0c;对于思维的考察较多。
思路#xff1a;
1.首先我们想想什么情况下该树不存在#xff1f;
由二叉树的性质可知每一个子节点个数为2的树都必须有两个#xff0c;每一个子节点为1的树必须有…题目链接0, 1, 2, Tree!
本道题目其实就是一道贪心的题目对于思维的考察较多。
思路
1.首先我们想想什么情况下该树不存在
由二叉树的性质可知每一个子节点个数为2的树都必须有两个每一个子节点为1的树必须有1个那么最后的0也就是叶子节点的数量跟这两个有什么关系
先看一棵树 O / \ aO Oe 假设这么一棵树我们可以发现a的子节点有两个那么叶子节点就比 / \ | 这个节点多了1子节点为1的则就只有一个我们可以把d这个叶子节点 O O O 分给根节点这样每个子节点个数为2的节点都有2个叶子节点。 b c d 所以可以知道当叶子节点个数 子节点个数为2的节点个数 1 2.怎么贪心的去考虑这棵树
换种问法如何合理分配这三种节点首先0肯定是叶子节点所以不用考虑那就考虑如何分配这两种节点使树的高度最小 O O / \ | O O O / \ / \ / \ O O O O O O / \ | | / \ / \ O O O O O O O O | O
从这两棵树中我们可以清晰的发现要使得高度最小那肯定是先放子节点个数为2的再去放1的。
那么思路到这边就结束了。
代码如何实现以及一些细节
#include bits/stdc.h
#define int long long
using namespace std;
int a,b,c;void solve(){cinabc;if(a1!c){cout-1\n;return;}int h10;for(int i1;ia;i){if(pow(2,i)-1a){h1i-1;break;}}//couth1h1\n;int lessa-(pow(2,h1)-1);//还有多少个2//coutlessless\n;int cur_less(pow(2,h1)-less);//目前该行还有多少个1可以填//coutcurcur_less\n;int ppow(2,h1)less;//表示接下来还有多少点//coutpp\n;if(!less!b){//如果是满二叉树couth1\n;return;}if(cur_lessb){h1;couth1\n;}else{b-cur_less;h1;h1((b-1)/p1);couth1\n;}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cint;while(t--){solve();}return 0;
}
