package leetcode.oj.triangle;

import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * Created by mark on 2/10/14.
 */

public class Solution {
    static int sum = 0;

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        Node head = convertToTree(triangle);
        getMaxSumByPath(head,0);
        return sum;
    }

    public void getMaxSumByPath(Node node,int newValue) {
        if (node.left == null && node.right == null) {
            int newSum = newValue + node.val;
            if (sum == 0)
                sum = newSum;
            else if (sum < newSum)
                sum = newSum;
        } else if (node.left != null) {
            getMaxSumByPath(node.left,newValue+node.val);
        } else if (node.right != null) {
            getMaxSumByPath(node.right,newValue+node.val);
        }
    }

    public Node convertToTree(ArrayList<ArrayList<Integer>> triangle) {
        int height = triangle.size();
        ArrayDeque<Node> queue = new ArrayDeque<Node>();
        Node cnode = new Node(triangle.get(0).get(0), 0, 0);
        Node head = cnode;
        queue.addLast(cnode);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.i == height - 1) {
                continue;
            } else {
                Node left = new Node(triangle.get(node.i + 1).get(node.j), node.i + 1, node.j);
                Node right = new Node(triangle.get(node.i + 1).get(node.j + 1), node.i + 1, node.j + 1);
                node.left =left;
                node.right = right;
                queue.addLast(left);
                queue.addLast(right);
            }
        }
        return head;
    }

    class Node {
        public Node(int val, int i, int j) {
            this.val = val;
            this.i = i;
            this.j = j;
        }

        int val;
        int i;
        int j;
        Node left = null;
        Node right = null;
    }
}

@@ -149,32 +149,8 @@
 on %7B
-%0A    static int sum = 0;
 %0A%0A  
@@ -229,1695 +229,473 @@
     
-Node head = convertToTree(triangle);%0A        getMaxSumByPath(head,0);%0A        return sum;%0A    %7D%0A%0A    public void getMaxSumByPath(Node node,int newValue) %7B%0A        if (node.left == null && node.right == null) %7B%0A            int newSum = newValue + node.val;%0A            if (sum == 0)%0A                sum = newSum;%0A            else if (sum %3C newSum)%0A                sum = newSum;%0A        %7D else if (node.left != null) %7B%0A            getMaxSumByPath(node.left,newValue+node.val);%0A        %7D else if (node.right != null) %7B%0A            getMaxSumByPath(node.right,newValue+node.val);%0A        %7D%0A    %7D%0A%0A    public Node convertToTree(ArrayList%3CArrayList%3CInteger%3E%3E triangle) %7B%0A        int height = triangle.size();%0A        ArrayDeque%3CNode%3E queue = new ArrayDeque%3CNode%3E();%0A        Node cnode = new Node(triangle.get(0).get(0), 0, 0);%0A        Node head = cnode;%0A        queue.addLast(cnode);%0A        while (!queue.isEmpty()) %7B%0A            Node node = queue.poll();%0A            if (node.i == height - 1) %7B%0A                continue;%0A            %7D else %7B%0A                Node left = new Node(triangle.get(node.i + 1).get(node.j), node.i + 1, node.j);%0A                Node right = new Node(triangle.get(node.i + 1).get(node.j + 1), node.i + 1, node.j + 1);%0A                node.left =left;%0A                node.right = right;%0A                queue.addLast(left);%0A                queue.addLast(right);%0A            %7D%0A        %7D%0A        return head;%0A    %7D%0A%0A    class Node %7B%0A        public Node(int val, int i, int j) %7B%0A            this.val = val;%0A            this.i = i;%0A            this.j = j;%0A        %7D%0A%0A        int val;%0A        int i;%0A        int j;%0A        Node left = null;%0A        Node right = null;%0A    %7D
+int%5B%5D%5B%5D data = new int%5Btriangle.size()%5D%5Btriangle.size()%5D;%0A        int length = triangle.size();%0A%0A        for (int i = 0; i %3C length; i++) %7B%0A            data%5Blength - 1%5D%5Bi%5D = triangle.get(length - 1).get(i);%0A        %7D%0A%0A        for (int j = length - 2; j %3E -1; j--) %7B%0A            for (int k = 0; k %3C= j; k++) %7B%0A                data%5Bj%5D%5Bk%5D = triangle.get(j).get(k) + Math.min(data%5Bj + 1%5D%5Bk%5D, data%5Bj + 1%5D%5Bk + 1%5D);%0A            %7D%0A        %7D%0A        return data%5B0%5D%5B0%5D;%0A    %7D%0A
 %0A%7D%0A

add solution