回溯算法 求解最短路径

需求:
有一个正三角形,类似“杨辉三角”,但是每个位置的数字可以随意填写,经过某个数字只能到达下面一层相邻的两个数字。
假设你站在第一层,往下移动,我们把移动到最底层所经过的所有数字之和,定义为路径的长度。
请你编程求出从最高层移动到最底层的最短路径长度。

分析:
路径类似这种

        
        			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;

    }
}