需求:
有一个正三角形,类似“杨辉三角”,但是每个位置的数字可以随意填写,经过某个数字只能到达下面一层相邻的两个数字。
假设你站在第一层,往下移动,我们把移动到最底层所经过的所有数字之和,定义为路径的长度。
请你编程求出从最高层移动到最底层的最短路径长度。
分析:
路径类似这种
10
11 12
5 6 7 8
1 2 3 4 5 6 7 8
从顶点向下走,那么每个点有两种走法,向左下或者向右下,这明显要用递归来逐层处理。
这里不同于常见的最短路径题,起点和终点是固定的各自一个点,这里起点是一个点,终点是多个点,从而要找出最短路径。
总结一下问题的本质是:路径的整体的结构就是一个满二叉树,求从顶点到哪一个叶子节点的路径最短,求的是单起点多终点的最短路径。
看代码:
import lombok.Data;
import java.util.Objects;
/**
* 回溯算法 求解最短路径
*
*
*/
public class YangHuiSanJiao {
private static int min = Integer.MAX_VALUE;
public static void main(String[] args) {
/*
10
11 12
5 6 7 8
1 2 3 4 5 6 7 8
*/
YangHuiSanJiaoInner d1 = new YangHuiSanJiaoInner();
d1.setValue(10);
YangHuiSanJiaoInner d2 = new YangHuiSanJiaoInner();
d2.setValue(11);
YangHuiSanJiaoInner d3 = new YangHuiSanJiaoInner();
d3.setValue(12);
YangHuiSanJiaoInner d4 = new YangHuiSanJiaoInner();
d4.setValue(5);
YangHuiSanJiaoInner d5 = new YangHuiSanJiaoInner();
d5.setValue(6);
YangHuiSanJiaoInner d6 = new YangHuiSanJiaoInner();
d6.setValue(7);
YangHuiSanJiaoInner d7 = new YangHuiSanJiaoInner();
d7.setValue(8);
YangHuiSanJiaoInner d8 = new YangHuiSanJiaoInner();
d8.setValue(1);
YangHuiSanJiaoInner d9 = new YangHuiSanJiaoInner();
d9.setValue(2);
YangHuiSanJiaoInner d10 = new YangHuiSanJiaoInner();
d10.setValue(3);
YangHuiSanJiaoInner d11 = new YangHuiSanJiaoInner();
d11.setValue(4);
YangHuiSanJiaoInner d12 = new YangHuiSanJiaoInner();
d12.setValue(5);
YangHuiSanJiaoInner d13 = new YangHuiSanJiaoInner();
d13.setValue(6);
YangHuiSanJiaoInner d14 = new YangHuiSanJiaoInner();
d14.setValue(7);
YangHuiSanJiaoInner d15 = new YangHuiSanJiaoInner();
d15.setValue(8);
d1.setLeft(d2);
d1.setRight(d3);
d2.setLeft(d4);
d2.setRight(d5);
d3.setLeft(d6);
d3.setRight(d7);
d4.setLeft(d8);
d4.setRight(d9);
d5.setLeft(d10);
d5.setRight(d11);
d6.setLeft(d12);
d6.setRight(d13);
d7.setLeft(d14);
d7.setRight(d15);
getMin(d1,0);
System.out.println("最短路径长度:" + min);
}
/**
* 回溯求解
* 结果:最短路径长度:26
* @param yhsj
* @param value
*/
public static void getMin(YangHuiSanJiaoInner yhsj, int value) {
if(Objects.isNull(yhsj.getLeft()) && value < min) {
min = value;
return;
}
if(Objects.isNull(yhsj.getRight()) && value < min) {
min = value;
return;
}
if(Objects.nonNull(yhsj.getLeft())) {
getMin(yhsj.getLeft(), yhsj.getValue()+value);
}
if(Objects.nonNull(yhsj.getRight())) {
getMin(yhsj.getRight(), yhsj.getValue()+value);
}
}
@Data
static class YangHuiSanJiaoInner {
private int value;
private YangHuiSanJiaoInner left;
private YangHuiSanJiaoInner right;
}
}