Reverse Linked List II LeetCode

Find the start and end node for reversing.


public ListNode reverseBetween(ListNode head, int m, int n) {
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      ListNode temp = dummy;
     
      int index = 1;
      while (index < m) {
          temp = temp.next;
          index++;
      }
      ListNode prev = temp;
      ListNode newHead = temp.next;
      while (index <= n) {
          temp = temp.next;
          index++;
      }
      ListNode end = temp.next;
      prev.next = reverse(newHead, end);
      return dummy.next;
    }
   
    private ListNode reverse(ListNode head, ListNode end) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != end) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

Unique Binary Search Trees II LeetCode

Recursion could simplify the code significantly.
The returning result is all the root node of each Tree.

public List<TreeNode> generateTrees(int n) {
        return generateTrees(1,n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
       
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i=start; i<=end; i++) {
            for (TreeNode left : generateTrees(start, i-1)) {
                for (TreeNode right : generateTrees(i+1, end)) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = left;
                    curr.right = right;
                    result.add(curr);
                }
            }
        }
        return result;
    }

Maximum

DP
but we only need two variables to store the maxvalue and minvalue

public int maxProduct(int[] A) {
        if (A.length == 1) return A[0];
        int maxProduct = A[0];
        int currMax = A[0];
        int currMin = A[0];
       
        for (int i=1; i<A.length; i++) {
            int temp = currMax;
            currMax = Math.max(Math.max(temp*A[i], A[i]), currMin*A[i]);
            currMin = Math.min(Math.min(currMin*A[i], A[i]), temp*A[i]);
            maxProduct = Math.max(maxProduct, currMax);
        }
        return maxProduct;
    }

Word Break LeetCode

dp
dp[j] = dp[i] && dict.contains(s.substring(j,i))

public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
       
        for (int i=1; i<=s.length();i++) {
            for (int j=0; j<i; j++) {
                if (dp[j] && dict.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

Construct Binary Tree from preOrder and inOrder Leetcode

Similarly, copy the solution from postOrder and inOrder.

public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(preorder == null || inorder == null) return null;
        if(preorder.length == 0 || inorder.length == 0) return null;
        return build (preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

        public TreeNode build(int[] preorder, int start1, int end1, int[] inorder, int start2,
int end2) {
        if(start1 > end1 || start2 > end2) return null;
int current = preorder[start1];
TreeNode currRoot = new TreeNode(current);
        int k = start2;
        for(; k < inorder.length; k++)
        if(inorder[k] == current) break;
        currRoot.left = build(preorder, start1+1, start1-start2+k, inorder, start2, k-1);
        currRoot.right = build(preorder, start1-start2+k+1,end1, inorder, k+1, end2);
        return currRoot;
    }

Construct Binary Tree from Inorder and PostOrder LeetCode

The last element from postOrder is the root value.

Find the last element from inOrder, Will get the length of subTrees.

public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null || postorder == null) return null;

        if (inorder.length == 0 || postorder.length == 0) return null;

        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

}

private TreeNode buildTree(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {

   if (start1 > end1 || start2 > end2) return null;

   int currentValue = postorder[end2];

   TreeNode currRoot = new TreeNode(currentValue);

   int k = start1;

   for (; k < inorder.length; k++) {

       if (inorder[k] == currentValue) break;

   }

   currRoot.left = buildTree(inorder, start1, k-1, postorder, start2, end2-end1+k-1);

   currRoot.right = buildTree(inorder, k+1, end1, postorder, end2-end1+k, end2-1);

   return currRoot;

}

Convert Sort List to Binary Search Tree LeetCode

The start position for fast and slow should be set carefully.

public TreeNode sortedListToBST(ListNode head) {

        if (head == null) return null;

        if (head.next == null) return new TreeNode(head.val);

        

        ListNode fast = head.next.next;

        ListNode slow = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        ListNode parent = slow.next;

        slow.next = null;

        TreeNode root = new TreeNode(parent.val);

        root.left = sortedListToBST(head);

        root.right = sortedListToBST(parent.next);

        

        return root;

    }

Here is a better solution. (Bottom-up)

From the CleanCodeHandbook of LeetCode.
public class Solution {
    private ListNode list;
    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        ListNode p = head;
        while (p!=null) {
            p = p.next;
            n++;
        }
        list = head;
        return sortedListToBST(0, n-1);
    }
   
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = (start + end)/2;
        TreeNode leftChild = sortedListToBST(start, mid-1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = leftChild;
        list = list.next;
        TreeNode rightChild= sortedListToBST(mid+1, end);
        parent.right = rightChild;
        return parent;
       
    }
}