Minimum Depth of Binary Tree LeetCode

Recursion:
public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.left != null && root.right != null) {
            return 1+Math.min(minDepth(root.left), minDepth(root.right));
        }
        else if (root.left == null && root.right != null) {
            return 1+minDepth(root.right);
        } else {
        return 1+minDepth(root.left);
        }
    }

Non-Recursion:
Why we use this method. Sometimes the tree is not balanced. This way will save lots of time. The worst of time complexity is O(n).
public int minDepth(TreeNode root) {
        if (root == null) return 0;
     
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> intQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        intQueue.add(1);
     
        while (!nodeQueue.isEmpty()) {
            TreeNode currNode = nodeQueue.poll();
            int currDepth = intQueue.poll();
         
            if (currNode.left != null) {
                nodeQueue.add(currNode.left);
                intQueue.add(currDepth+1);
            }
            if (currNode.right != null) {
                nodeQueue.add(currNode.right);
                intQueue.add(currDepth+1);
            }
            if (currNode.right == null && currNode.left == null) {
                return currDepth;
            }
        }
        return -1;//Should never reach here.
    }

Path Sum LeetCode

Recursion:
public boolean hasPathSum(TreeNode root, int sum) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (root == null) return false;
        if (root.left == null && root.right == null && sum == root.val) {
            return true;
        } else {
            return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
        }
       
    }

Non-recursion:
public boolean hasPathSum(TreeNode root, int sum) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       if (root==null) return false;
     
       Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
       Queue<Integer> intQueue = new LinkedList<Integer>();
       nodeQueue.add(root);
       intQueue.add(root.val);
     
       while (!nodeQueue.isEmpty()) {
           TreeNode currNode = nodeQueue.poll();
           int currVal = intQueue.poll();
         
           if (currNode.left == null && currNode.right == null && sum == currVal) {
               return true;
           }
           if (currNode.left != null) {
               nodeQueue.add(currNode.left);
               intQueue.add(currVal + currNode.left.val);
           }
           if (currNode.right != null) {
               nodeQueue.add(currNode.right);
               intQueue.add(currVal + currNode.right.val);
           }
       }
       return false;
     
    }

Pascal's Triangle LeetCode

Check Pascal's Triangle


public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (numRows < 1) return result;
        if (numRows == 1) {
            List<Integer> currList = new ArrayList<Integer>();
            currList.add(1);
            result.add(currList);
            return result;
        }
       
        List<List<Integer>> lastResult = generate(numRows-1);
        result.addAll(lastResult);
        List<Integer> lastList = lastResult.get(lastResult.size() - 1);
        List<Integer> newList = new ArrayList<Integer>();
        newList.add(1);
        for (int i=0; i<lastList.size()-1; i++) {
            newList.add(lastList.get(i) + lastList.get(i+1));
        }
        newList.add(1);
        result.add(newList);
        return result;
    }

Pascal's Triangle II Leetcode

Trivial solution without considering space
 public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        if (rowIndex == 0) {
            result.add(1);
            return result;
        }
       
        List<Integer> currList = getRow(rowIndex - 1);
        List<Integer> newList = new ArrayList<Integer>();
        newList.add(1);
        for (int i = 0; i < currList.size() - 1; i++) {
            newList.add(currList.get(i) + currList.get(i+1));
        }
        newList.add(1);
        return newList;
    }

Consider about the space.
Collections.nCopies(n,0) is a smart way to initialize the arraylist as zero.

public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(Collections.nCopies(rowIndex+1,0));
       
        result.set(0,1);
        for (int i=0; i<=rowIndex; i++) {
            result.set(i,1);
            for (int j=i-1; j>0; j--) {
                result.set(j, result.get(j)+result.get(j-1));
            }
        }
        return result;
    }

Symmetric Tree LeetCode

Recursively:

public class Solution {
    public boolean isSymmetric(TreeNode root) {
       if (root == null) return true;
       return isSymmetric(root.left, root.right);
    }
   
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val ) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
   
}

Iteratively:

public boolean isSymmetric(TreeNode root) {
       if (root == null || root.left == null && root.right == null) return true;
     
       Queue<TreeNode> lq = new LinkedList<TreeNode>();
       Queue<TreeNode> rq = new LinkedList<TreeNode>();
       lq.add(root.left);
       rq.add(root.right);
       TreeNode leftTreeNode = null;
       TreeNode rightTreeNode = null;
     
       while (lq.isEmpty() == false && rq.isEmpty() == false) {
           leftTreeNode = lq.poll();
           rightTreeNode = rq.poll();
         
           if (leftTreeNode == null && rightTreeNode == null) {
               continue;
           }
           if ((leftTreeNode == null && rightTreeNode != null )|| (leftTreeNode != null && rightTreeNode == null)) {
               return false;
           }
           if (leftTreeNode.val != rightTreeNode.val) {
               return false;
           }
         
           lq.add(leftTreeNode.left);
           lq.add(leftTreeNode.right);
         
           rq.add(rightTreeNode.right);
           rq.add(rightTreeNode.left);
         
       }
       return (lq.isEmpty()&&rq.isEmpty());
    }

LeetCode Maximum Subarray

General solution.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int runningSum = 0;
       int totalSum = A[0];
       for (int i = 0; i < A.length; i++) {
           runningSum += A[i];
           if (runningSum > 0) {
               totalSum = Math.max(runningSum, totalSum);
           } else {
               totalSum = Math.max(totalSum, A[i]);
               runningSum = 0;
           }
       }
       return totalSum;
    }

DP
Memory optimization
public int maxSubArray(int[] A) {
        int maxEndingHere = A[0], maxSoFar = A[0];
        for (int i=1; i<A.length; i++) {
            maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
            maxSoFar = Math.max(maxEndingHere, maxSoFar);
        }
        return maxSoFar;
    }


D&C
Implement the binary search everywhere.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int maxSum = Integer.MIN_VALUE;
       return findMaxSub(A, 0, A.length - 1, maxSum);
    }
 
    //Recursive to find max sum
    //may appear on the left, right or crossing the mid point
    private int findMaxSub(int[] A, int left, int right, int maxSum) {
        if (left > right) return Integer.MIN_VALUE;
     
        //Get Max sub by recursive ways
        int mid = (left + right)/2;
        int leftMax = findMaxSub(A, left, mid-1, maxSum);
        int rightMax = findMaxSub(A, mid+1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
     
        //GEt Max sum by crossing mid
        int lSum = 0;
        int midLeftMax = 0;
        for (int i = mid-1; i>=left; i--) {
            lSum = lSum + A[i];
            if (lSum > midLeftMax) midLeftMax = lSum;
        }
     
        int rSum = 0;
        int midRightMax = 0;
        for (int i = mid+1; i<=right; i++) {
            rSum = rSum + A[i];
            if (rSum > midRightMax) midRightMax = rSum;
        }
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        return maxSum;
    }