LeetCode（120）：三角形最小路径和
LeetCode（120）：三角形最小路径和Medium！
题目描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
,
,
,
]
自顶向下的最小路径和为 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.length ; j ++){
tree.add(new Node(array));
}
}
int index = 0;
for(int i = 0 ; i < array.length-1; i++){
for(int j = 0 ; j < array.length ; j++){
tree.get(index).leftChild = tree.get(index+ array.length);
tree.get(index).rightChild = tree.get(index +1 + array.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
页:
[1]