算法题——二叉树最小叶子节点到根节点的路径（数组）_二叉树根节点到叶子结点的路径和的最小值

---

戒言

座右铭：

Ctrl + C 可以复制得了别人的代码，但永远复制不了别人的人生和成功。
改变的确很难，但结果值得努力一试。
学习和工作的目的不仅仅是获得回报，也是自我经验的积累和技术的提升。
技术永远不会止步，止步的只有懈怠的我们。
有的人的确不是天生的将军，但也不是天生的士兵。

---

步入正文

一、今日学习

学习内容：
昨天遇到一道算法题，思索良久，不过值得一提的是，这算是我进入专业领域的第一道算法题，所以进行一个纪念，日后争取花更少的时间去完成算法题，感觉刷算法题时是对逻辑能力和耐心的考量，虽然这道题花的时间很久，但是很庆幸我自己没有放弃，所以还是要不断学习。
同样，最近不止在算法上花费时间，在Java的多线程学习中也有所投入，网络上的视频也观看了很多，同时对于一些底层的原理也越发得感兴趣，现在只是觉得时间如果可以慢一点就好了，让我有更多的时间花在我感兴趣的事物上，而不是为了完成学校的教学任务而去学习。

二、学习笔记

遇到的题目的内容是：
题目描述
二叉树也可以用数组来存储，给定一个数组，树的根节点的值储存在下标1， 对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2n和2n+1， 并且我们用-1代表一个节点为空。 给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。
输入
输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割。 注意第一个元素即为根节点的值，即数组的第n元素对应下标n。下标0在树的表示中没有使用，所以我们省略了。 输入的树最多为7层。
输出
输出从根节点到最小叶子节点的路径上各个节点的值由空格分割用例保证最小叶子节点只有一个
样例输入
3 5 7 -1 -1 2 4
样例输出
3 7 2

1.代码

代码如下：

import java.util.List;
import java.util.Scanner;
import java.util.Vector;

public class suanfatest {
    public static void main(String[] args) {
        int [] list = new int[127];//题目中说最多为7层，所以数组的长度设置为最大2^7-1
        List<Integer> list1 = new Vector<>();//创建一个动态数组list1用来存放路径
        Scanner in = new Scanner(System.in);//创建一个键盘扫描器
        String[] str = in.nextLine().split(" ");//从输入中读取一行字符串，然后使用空格作为分隔符将字符串拆分成多个子字符串，并将这些子字符串存储在一个字符串数组  str  中
        in.close();//关闭扫描器防止内存泄露
        int j=0;
        for (String s:str){
            list[j]=Integer.parseInt(s);
            j++;
        }//遍历字符串，提取元素到list数组中
        int yezijiedian =0;//初始化叶子节点为0
        for (int i = 0; i < list.length-2; i++) {
            if (list[i+1]==0){
                yezijiedian =i;
                break;
            }
        }//根据输入最后一个不为零的元素肯定是最后一层的叶子
        if (yezijiedian % 2==0){
            if(list[yezijiedian] >list[yezijiedian-1]){
                yezijiedian=yezijiedian-1;//叶子节点左移一位
            }
        }//如果最后这个叶子是右叶子的话并且它的左边比它小，那么更新叶子节点的值
        double ceng = Math.sqrt(yezijiedian);//获取叶子节点上一层数的近似值
        int cengshu = (int)Math.round(ceng);//对层数进行四舍五入取整
        double zuidiwei =Math.pow(2,cengshu)-1;//计算上一层对应的节点的个数
        if((int)zuidiwei > yezijiedian){
            cengshu =cengshu-1;//如果个数大于索引值，说明层数超了，那么层数就要减一
            zuidiwei=Math.pow(2,cengshu)-1;//等比数列求和公式 A1*（1-q^n）/（1-q）
            int min = list[yezijiedian];//把叶子节点对应的值存进去
            for (int i =yezijiedian-1;i>=zuidiwei;i--) {
                if (list[i] < min && list[i]!=-1){
                    min=list[i];
                    yezijiedian=i ;
                }
                if (i < zuidiwei){
                    break;
                }
            }
        }else {
            int min = list[yezijiedian];
            for (int i = yezijiedian - 1; i >= zuidiwei; i--) {
                if (list[i] < min && list[i] != -1) {
                    min =list[i];
                    yezijiedian = i;
                }
                if (i < zuidiwei) {
                    break;
                }
            }
        }//叶子元素和同一层元素进行比较，找到对应值最小的那个叶子节点
        list1.add(list[yezijiedian]);//先把最小叶子节点加进去
        int fujiedian = 0;//初始化父亲节点
        if(yezijiedian%2 != 0){
            fujiedian = (yezijiedian-1)/2;//拿到叶子的父节点
            list1.add(list[fujiedian]);
        }else {
            fujiedian = (yezijiedian-2)/2;//拿到叶子的父节点
            list1.add(list[fujiedian]);
        }//叶子节点是父节点左右分支的两种之一，所以分情况讨论
        while (yezijiedian %2 !=0){
            if (fujiedian%2 == 0){
                fujiedian =(fujiedian-2)/2;
                list1.add(list[fujiedian]);
                if (fujiedian == 0){
                    break;
                }
            }//说明父节点是右分支
            if(fujiedian%2 !=0){
                fujiedian =(fujiedian-1)/2;
                list1.add(list[fujiedian]);
                if (fujiedian==0){
                    break;
                }
            }//说明父节点是左分支
        }//最小叶子节点是左节点情况
        while(yezijiedian %2 ==0 ){
            if (fujiedian%2 == 0){
                fujiedian =(fujiedian-2)/2;
                list1.add(list[fujiedian]);
                if (fujiedian==0){
                    break;
                }
            }//说明父节点是右分支
            if(fujiedian%2 !=0){
                fujiedian =(fujiedian-1)/2;
                list1.add(list[fujiedian]);
                if (fujiedian==0){
                    break;
                }
            }//说明父节点是左分支
        }//最小叶子节点是右节点情况
        for (int i = list1.size() - 1; i >= 0; i--) {
            System.out.printf("%d"+" ",list1.get(i));
        }//对路径数组进行倒序打印
    }
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

2.笔记

 1. 
这道算法题涉及到二叉树的概念、动态数组的创建以及Java的基本语法，该部分有待完善和提高，同时这道题的正确解法还不确定，如果有读者发现错误请指出并给予宝贵意见，在这里表示感谢。






总结
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
1
2
3
4
5
6
7
8
9
10
11

三、总结

数的图结构