算法——小球下落（二叉树）

客官°小女子只卖身不卖艺 2021-10-14 01:56 413阅读 0赞

**问题描述 :**

有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右 编号为1, 2, 3,…, 2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关， 初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。

如图所示：

![70][]

**样式输入：**

4 2
    3 4
    10 1
    2 2
    8 128
    16 12345

**样式输出：**

12
    7
    512
    3
    255
    36358

**解题思路：**

**    本题原先采用利用数组存储二叉树节点，但是会造成大量空间浪费。**

**    所以我们假设只有2个球，深度2第一个球很明显就落在1号根节点的左子树上，第二个球落在1号根节点的右子树上。因此可以推论，只要看球个数的奇偶性，便可以计算出它最终是落在哪个子树上。如果球的个数是奇数，便落在(num+1)/2的左子树上。如果球的个数是偶数，便落在num/2的右子树上。**

**实现：**

import java.util.Scanner;
    
    /**
     * 小球落地问题
     *
     * @Classname BallFall
     * @Description TODO
     * @Date 2019/8/17 14:50
     * @Created zzf
     */
    public class BallFall {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            //深度
            int depth = sc.nextInt();
            //第num个球
            int num = sc.nextInt();
            //初始化
            int data = 1;
            //计算层数为1~dapth-1
            for (int i = 1; i <= depth - 1; i++) {
                //如果有余数则这个球在左边，否则在右边
                if (num % 2 == 1) {
                    //计算,因为在左边*2
                    data *= 2;
                    //计算下一个标号的位置
                    num = (num + 1) / 2;
                } else {
                    //计算,右边比左边大1
                    data = data * 2 + 1;
                    num /= 2;
                }
    //            System.out.println(data);
            }
            System.out.println(data);
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

[70]: /images/20211013/e179d3aaafc847bda53fb8b356204d69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20211013/099c6d324d0a4a9f80ad3da528f93852.png