回溯算法 求解最短路径

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

分析：
路径类似这种

        
        			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;

    }
}