首页 > 试题广场 >

加减二叉树

[编程题]加减二叉树
  • 热度指数：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。
算法知识视频讲解
开通博客

暂无题解

问题信息

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

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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