首页 > 试题广场 >

加减二叉树

[编程题]加减二叉树
  • 热度指数：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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 树 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 区块链 模拟 测试开发工程师 2019 数学 大数据开发工程师 数据分析师 Java工程师 牛客
来自：2019校招-留学生招...
上传者：小小
难度：
2条回答 5230浏览

热门推荐

通过挑战的用户

相关试题

加减二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号