LeetCode（120）：三角形最小路径和

Seawolf

LeetCode（120）：三角形最小路径和
Medium！

题目描述：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class main {

    private int array[][] = {{-1},{2,3},{1,-1,-3}};

    private static List<Node> tree = null;

    private static int min = 100000;

    private static int minNode = 100000;

    private static class Node{

        Node leftChild;

        Node rightChild;

        int data;

        Node(int newData){

            leftChild = null;

            rightChild = null;

            data = newData;

        }
    }

    public void createTree(){

        tree = new LinkedList<Node>();

        for(int i = 0 ; i < array.length; i ++){

            for(int j = 0; j < array[i].length ; j ++){

                tree.add(new Node(array[i][j]));
            }

        }

        int index = 0;
        for(int i = 0 ; i < array.length-1; i++){

            for(int j = 0 ; j < array[i].length ; j++){
                
                tree.get(index).leftChild = tree.get(index  + array[i].length);
                tree.get(index).rightChild = tree.get(index +1 + array[i].length);
                index ++ ;

            }

        }
    }

    public static void inorderTraverse(Node node){

        if(node == null){

            return;
        }
        
        inorderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        inorderTraverse(node.rightChild);
        
    }

    public static void preorderTraverse(Node node){

        if(node == null){

            return;
        }

        System.out.print(node.data + " ");
        preorderTraverse(node.leftChild);
        preorderTraverse(node.rightChild);

    }

    public static void postorderTraverse(Node node){

        if(node == null){

            return;
        }
        
        postorderTraverse(node.leftChild);
        postorderTraverse(node.rightChild);
        System.out.print(node.data + " ");
    }

    public static void dfs(Node node,int sum) {

        if (node != null) {

            if (node.rightChild == null && node.leftChild == null) {
                
                if (sum + node.data < min || (sum + node.data == min && node.data < minNode)) {

                    min = sum + node.data;
                    minNode = node.data;

                }

            }
            dfs(node.leftChild, sum + node.data);
            dfs(node.rightChild, sum + node.data);
        }
    }

    public static void main(String[] args){

        main test = new main();

        test.createTree();

        Node root = tree.get(0);
        dfs(root,0);

        System.out.println("minimum value!");

        System.out.println(min);
        System.out.println(minNode);
        System.out.println(minNode);

        System.out.println("in order traverse!");
        inorderTraverse(root);
        System.out.println();

        System.out.println("pre order traverse!");
        preorderTraverse(root);
        System.out.println();

        System.out.println("post order traverse!");
        postorderTraverse(root);
        System.out.println();
    }
}

output：

minimum value!
-1
-3
in order traverse!
1 2 -1 -1 -1 3 -3 
pre order traverse!
-1 2 1 -1 3 -1 -3 
post order traverse!
1 -1 2 -1 -3 3 -1