My solution using binary tree. (A little long.)


  • 0
    Q
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
    		if (triangle.size() == 1){
                return triangle.get(0).get(0);
            }
            TreeNode root = new TreeNode(triangle.get(0).get(0), 0, 0);
    		HashMap<TreeNode, TreeNode> visited = new HashMap<TreeNode, TreeNode>();
    		constructTree(root, 0, triangle, 1, visited);
    		
    		return root.min;
        }
        private void constructTree( TreeNode parent, int parentIndex, List<List<Integer>> triangle, int level,
    			Map<TreeNode, TreeNode> visited){
    		int leftChildIndex = parentIndex;
    		int rightChildIndex = parentIndex+1;
    		List<Integer> myLevelList = triangle.get(level);
    		TreeNode leftNode = new TreeNode(myLevelList.get(leftChildIndex), level, leftChildIndex);
    		TreeNode rightNode = new TreeNode(myLevelList.get(rightChildIndex), level, rightChildIndex);
    
    		int newLevel = level+1;
    		
    		if (visited.containsKey(leftNode)){
    			leftNode = visited.get(leftNode);
    		}
    		else{
    			if (newLevel < triangle.size()){
    				constructTree(leftNode, leftChildIndex, triangle, newLevel, visited);
    			}
    			visited.put(leftNode, leftNode);
    		}
    		
    		if (visited.containsKey(rightNode)){
    			rightNode = visited.get(rightNode);
    		}
    		else{
    			if (newLevel < triangle.size()){
    				constructTree(rightNode, rightChildIndex, triangle, newLevel, visited);
    			}
    			visited.put(rightNode, rightNode);
    		}
    		parent.left = leftNode;
    		parent.right = rightNode;
    		
    		if (newLevel == triangle.size()){
    			leftNode.min = leftNode.value;
    			rightNode.min = rightNode.value;
    		}
    		parent.min = parent.value + Math.min(leftNode.min, rightNode.min);
    	}
    	
    	private class TreeNode{
    		int min = 0;
    		int level = 0;
    		int position = 0;
    		TreeNode left;
    		TreeNode right;
    		Integer value;
    		
    		public TreeNode(Integer i, int level, int position){
    			this.value = i;
    			this.level = level;
    			this.position = position;
    		}
    		public boolean equals(Object treeNode){
    			TreeNode other = (TreeNode)treeNode;
    			if (other.level == this.level && other.position == this.position){
    				return true;
    			}
    			return false;
    		}
    		public int hashCode(){
    			return level*100 + position;
    		}
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.