实验三 0-1-2树_找出具有a+b+c个节点且高度最小的二叉树,满足以下条件: a个节点具有2个子节点 b个

---

我只能说做这种题真的太折磨了！！！

但是想通了还是很简单的，就是需要一点逻辑思维。

---

找出具有a+b+c个节点且高度最小的二叉树，满足以下条件：

a个节点具有2个子节点

b个节点具有1个子节点

c个节点没有子节点
如果不存在这样的树，则输出-1， 否则输出树的高度。

图示为a=2、b=1、c=3的满足条件的树，其高度为2。 树的高度是指从根节点到最底层叶节点之间的边数之和。

输入形式

输入的第一行为T，表示有T个测试样例，接下来的T行，每行3个整数a、b、c(0≤a、b、c≤10^5,
a+b+c≥1)，分别表示所构成的树有a+b+c个节点，其中a个节点具有2个子节点，b个节点具有1个子节点，c个节点没有子节点。

输出形式

输出为T行，每行一个整数，表示满足条件的树的最小高度，如果不存在这样的树，则输出-1。

样例输入

10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1

样例输出

2
0
1
1
-1
3
6
-1
-1
3

---

怎么说呢，最基本的思路还是要有的，不然神仙都救不了你了。
基本思路：
因为要让树的高度尽可能小，那么度越大的肯定要放在靠上的位置。
c节点一定是在最下面的，度都为0了怎么弄子节点。
加入先处理b节点，一个节点只有一个子节点，那高度不得嘎嘎增加。
所以，
先放a节点,再放b节点,最后处理c节点嘎嘎简单。

---

那就直接上代码吧，跟着代码和注释更好懂哦
实在不懂的话评论区留言哦

---

#include<iostream>
#include <cmath>
using namespace std;
int num[2];//用来记录上一层有多少个a节点和b节点
int main()
{
    int T;
    cin>>T;
    int a,b,c;
    while(T--)
    {
        num[0]=0,num[1]=0;//初始化
        cin>>a>>b>>c;
        if(a+1!=c)//度为0的节点比度为2的节点多1
        {
            cout<<-1<<endl;
            continue;
        }
        if(a==0&&b==0&&c==1)//特殊情况判断
        {
            cout<<0<<endl;
            continue;
        }
        int h=0;//高度初始化为0
        while(a!=0)//先处理a节点
        {
            num[0]=a;
            a-=pow(2,h);//若度为2，则第h层有2的h次个节点；
            if(a>=0)h++;//填满了第h层,h++；
            if(a<0)break;//如果填不满,就结束循环
        }
        if(b==0&&a==0)cout<<h<<endl;//若b=0,a=0，则空的部分只能填一层c
        else if(b==0&&a!=0)cout<<h+1<<endl;
        //这一层填了部分a，但是未填满,则这一层剩下的部分填c，且这一层的a还有子节点，
        //则下一层还要填
        else if(b<=-a)//如果b不能填满或者刚好填满a未填满的那一层，那下一层会有c
        //因为a=a-pow(2,h)，则-a=pow(2,h)-a，即为未填满的节点数
        {
            cout<<h+1<<endl;
        }
        else//b能填满且还剩下b
        {
            if(a!=0)//a那一层未填满
            {
                num[1]=-a;//填-a个
                b+=a;//a是负数，相当于b减小了
                h++;//这一层填满了，下一层一定会有
            }
            if(num[1]==0&&num[0]==0)num[1]=1;//前面未出现过a，则根节点为b
            while(b>0)
            {
                if(num[0]!=0)//上一层有a节点
                {
                    b-=num[0]*2+num[1];
                    num[1]=num[0]*2+num[1];
                    num[0]=0;
                }
                else
                {
                    b-=num[1];//a节点处理完了
                }
                if(b<=0)//b也处理完了，最后要加一层c，有且仅有一层
                {
                    cout<<h+1<<endl;
                    break;
                }
                h++;//这层填满了还有b，继续填下一层
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72