首页 > 试题广场 >

加减二叉树

[编程题]加减二叉树
  • 热度指数:332 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
二叉树是除了叶子节点之外所有的节点都最多有两个子节点的树。满二叉树则是除叶子节点外所有节点都有两个子节点的树,且所有叶子节点到根节点的距离都相等。

现在有一棵无限大的满二叉树,根节点编号为1。编号为i的节点的左儿子编号为2*i,右儿子2*i+1(比如根节点1的左儿子为2,右儿子为3,2的左儿子为4,右儿子为5。)。牛牛在这棵树上做一个游戏,他从妞妞那里得到了两个数n和k,妞妞希望他拿着数字0从根节点开始往下走,每次选择一条边移动,到达一个节点时选择加上这个节点的编号或者减去这个节点的编号。在走到第k个节点时所得到的数字刚好等于n。

这样的路径当然有很多。为了增加难度,妞妞决定让牛牛告诉她经过的节点的编号和最小的路径。
妞妞很聪明,给出的问题都是一定存在答案的。
你能帮帮牛牛吗?

输入描述:
一行,两个数字n,k。


输出描述:
共k行,第i行输出第i步到达的节点编号,如果加上这个编号输出' +',减去这个编号输出' -'。
示例1

输入

3 2

输出

1 +
2 +
示例2

输入

6 3

输出

1 -
2 +
5 +

备注:
1<=n<=1000000000。
1<=n<=2^k<=2^60。
#include<iostream>
#include<cmath>

using namespace std;

typedef long long int dataType;

int countMinPath(long long int n,int k,long long int *arry)
{
    for(long long int i = pow(2,k-1); i < pow(2,k-1)*2; i++)
    {
        long long int temp = n;
        long long int count = i;
        
        for(int j = k -1; j >= 0 && count != 0;j--) 
        {
            if(temp >= 0)
            {
                temp = temp - count;
                arry[j] = count;
            }
            else if(temp < 0)
            {
                temp = temp + count;
                arry[j] =  -count;
            }
            count = count/2;
        }    
        
        if(temp == 0)
            return 0;    
    }
}


int main()
{
    long long int n = 0;
    int k = 0;
    
    cin >> n >> k;
    long long int arry[60] = {0};
    countMinPath(n,k,arry);
    for(int i = 0;i < k;i++)
    {
        if(arry[i] >0)
            cout <<arry[i] <<" +"<<endl;
        else
            cout <<llabs(arry[i] )<<" -"<<endl;
    }
    return 0;
}

发表于 2019-07-18 21:24:48 回复(0)
#include<bits/stdc++.h>
using namespace std;
void process(long long n,long long k){
    vector<long long>ans;
    //从最后一步开始往上走,最后一步的取值范围是[pow(2,k-1),pow(2,k))
    for(long long i=pow(2,k-1);i<pow(2,k);i++){
        long long distance=n;    //记录当前的距离
        long long level=i;    //记录当前的数值,从编号小的数开始试
        for(long long j=k;j>0;j--){    //记录步数
            if(distance>0){
                distance-=level;
                ans.push_back(level);
            }
            else{
                distance+=level;
                ans.push_back(-level);
            }
            level=level/2;    //其根节点,即上一步都是/2
        }
        if(distance==0)    //直到根节点走到0
            break;
        else
            ans.clear();
    }
    //打印结果
    for(long long i=ans.size()-1;i>=0;i--){
        if(ans[i]>0)
            cout<<ans[i]<<" +"<<endl;
        else 
            cout<<-ans[i]<<" -"<<endl;
    }
}
int main(){
    long long n,k;
    cin>>n>>k;
    //处理
    process(n, k);
    return 0;
}

发表于 2022-03-07 21:31:12 回复(0)