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

Seawolf

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

题目描述：

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

例如，给定三角形：

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

1. import java.util.ArrayList;
   
2. import java.util.LinkedList;
   
3. import java.util.List;
   
4. 
   
5. public class main {
   
6. 
   
7.     private int array[][] = {{-1},{2,3},{1,-1,-3}};
   
8. 
   
9.     private static List<Node> tree = null;
   
10. 
    
11.     private static int min = 100000;
    
12. 
    
13.     private static int minNode = 100000;
    
14. 
    
15.     private static class Node{
    
16. 
    
17.         Node leftChild;
    
18. 
    
19.         Node rightChild;
    
20. 
    
21.         int data;
    
22. 
    
23.         Node(int newData){
    
24. 
    
25.             leftChild = null;
    
26. 
    
27.             rightChild = null;
    
28. 
    
29.             data = newData;
    
30. 
    
31.         }
    
32.     }
    
33. 
    
34.     public void createTree(){
    
35. 
    
36.         tree = new LinkedList<Node>();
    
37. 
    
38.         for(int i = 0 ; i < array.length; i ++){
    
39. 
    
40.             for(int j = 0; j < array[i].length ; j ++){
    
41. 
    
42.                 tree.add(new Node(array[i][j]));
    
43.             }
    
44. 
    
45.         }
    
46. 
    
47.         int index = 0;
    
48.         for(int i = 0 ; i < array.length-1; i++){
    
49. 
    
50.             for(int j = 0 ; j < array[i].length ; j++){
    
51.                
    
52.                 tree.get(index).leftChild = tree.get(index  + array[i].length);
    
53.                 tree.get(index).rightChild = tree.get(index +1 + array[i].length);
    
54.                 index ++ ;
    
55. 
    
56.             }
    
57. 
    
58.         }
    
59.     }
    
60. 
    
61.     public static void inorderTraverse(Node node){
    
62. 
    
63.         if(node == null){
    
64. 
    
65.             return;
    
66.         }
    
67.         
    
68.         inorderTraverse(node.leftChild);
    
69.         System.out.print(node.data + " ");
    
70.         inorderTraverse(node.rightChild);
    
71.         
    
72.     }
    
73. 
    
74.     public static void preorderTraverse(Node node){
    
75. 
    
76.         if(node == null){
    
77. 
    
78.             return;
    
79.         }
    
80. 
    
81.         System.out.print(node.data + " ");
    
82.         preorderTraverse(node.leftChild);
    
83.         preorderTraverse(node.rightChild);
    
84. 
    
85.     }
    
86. 
    
87.     public static void postorderTraverse(Node node){
    
88. 
    
89.         if(node == null){
    
90. 
    
91.             return;
    
92.         }
    
93.         
    
94.         postorderTraverse(node.leftChild);
    
95.         postorderTraverse(node.rightChild);
    
96.         System.out.print(node.data + " ");
    
97.     }
    
98. 
    
99.     public static void dfs(Node node,int sum) {
    
100. 
     
101.         if (node != null) {
     
102. 
     
103.             if (node.rightChild == null && node.leftChild == null) {
     
104.                
     
105.                 if (sum + node.data < min || (sum + node.data == min && node.data < minNode)) {
     
106. 
     
107.                     min = sum + node.data;
     
108.                     minNode = node.data;
     
109. 
     
110.                 }
     
111. 
     
112.             }
     
113.             dfs(node.leftChild, sum + node.data);
     
114.             dfs(node.rightChild, sum + node.data);
     
115.         }
     
116.     }
     
117. 
     
118.     public static void main(String[] args){
     
119. 
     
120.         main test = new main();
     
121. 
     
122.         test.createTree();
     
123. 
     
124.         Node root = tree.get(0);
     
125.         dfs(root,0);
     
126. 
     
127.         System.out.println("minimum value!");
     
128. 
     
129.         System.out.println(min);
     
130.         System.out.println(minNode);
     
131.         System.out.println(minNode);
     
132. 
     
133.         System.out.println("in order traverse!");
     
134.         inorderTraverse(root);
     
135.         System.out.println();
     
136. 
     
137.         System.out.println("pre order traverse!");
     
138.         preorderTraverse(root);
     
139.         System.out.println();
     
140. 
     
141.         System.out.println("post order traverse!");
     
142.         postorderTraverse(root);
     
143.         System.out.println();
     
144.     }
     
145. }
     

复制代码

output：

1. minimum value!
   
2. -1
   
3. -3
   
4. in order traverse!
   
5. 1 2 -1 -1 -1 3 -3
   
6. pre order traverse!
   
7. -1 2 1 -1 3 -1 -3
   
8. post order traverse!
   
9. 1 -1 2 -1 -3 3 -1

复制代码