Skip to content

Instantly share code, notes, and snippets.

@steven-zou

steven-zou/Balanced Binary Tree

Last active August 29, 2015 14:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save steven-zou/67e1eae2fad89b992b52 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save steven-zou/67e1eae2fad89b992b52 to your computer and use it in GitHub Desktop.
Download ZIP
Solution code for LeetCode problems
Raw
Balanced Binary Tree
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int l = getDepth(root.left);
int r = getDepth(root.right);
return Math.abs(l-r)<2 && isBalanced(root.left) && isBalanced(root.right);
}
public int getDepth(TreeNode node){
if(node==null){
return 0;
}
if(node.left==null && node.right==null){
return 1;
}
return 1+Math.max(getDepth(node.left), getDepth(node.right));
}
}
Raw
Construct Binary Tree from Inorder and Postorder Traversal
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
//Inorder: left->root->right
//postorder: left->right->root
if(inorder.length==0||postorder.length==0||inorder.length!=postorder.length){
return null;
}
int rootVal = postorder[postorder.length-1];
TreeNode root = new TreeNode(rootVal);
int i;
for(i=0;i<inorder.length;i++){
if(inorder[i]==rootVal){
break;
}
}
int leftNodeCount = i;
int rightNodeCount = inorder.length-1-i;
if(leftNodeCount>0){
int[] leftInorder = new int[leftNodeCount];
int[] leftPostorder = new int[leftNodeCount];
System.arraycopy(inorder, 0, leftInorder, 0, leftNodeCount);
System.arraycopy(postorder, 0, leftPostorder, 0, leftNodeCount);
root.left = buildTree(leftInorder, leftPostorder);
}
if(rightNodeCount>0){
int[] rightInorder = new int[rightNodeCount];
int[] rightPostorder = new int[rightNodeCount];
System.arraycopy(inorder, leftNodeCount+1, rightInorder, 0, rightNodeCount);
System.arraycopy(postorder, leftNodeCount, rightPostorder, 0, rightNodeCount);
root.right = buildTree(rightInorder, rightPostorder);
}
return root;
}
}
Raw
Gas Station
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas.length==0 || cost.length==0 || gas.length!=cost.length){
return -1;
}
int len = gas.length;
for(int i=0;i<len;i++){
int left = gas[i]-cost[i];
if(left<0){
continue;
}
for(int j=i+1;j<len+i+1;j++){
int index=j>=len?j-len:j;
if(index==i){
return i;
}
left+=gas[index]-cost[index];
if(left<0){
break;
}
}
}
return -1;
}
}
Raw
longest common prefix
public class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs==null || strs.length==0){
return "";
}
Arrays.sort(strs, new LenComparator());
String lcp = strs[0];
for(int i=0,len=strs.length;i<len;i++){
if(!strs[i].startsWith(lcp)){
lcp = lcp.substring(0, lcp.length()-1);
if(lcp==""){
break;
}
i=0;
}
}
return lcp;
}
private static class LenComparator implements Comparator<String>{
@Override
public int compare(String first, String second) {
return first.length()-second.length();
}
}
}
Raw
Maximum Depth of Binary Tree
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null && root.right==null){
return 1;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
Raw
Merge k sorted linked list
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if(lists.size()==0) return null;
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
for(ListNode ln : lists){
if(ln!=null){
q.add(ln);
}
}
ListNode head = new ListNode(0);
ListNode pre = head;
while(q.size()>0){
ListNode node = q.poll();
pre.next = node;
if(node.next!=null){
q.add(node.next);
}
pre = pre.next;
}
return head.next;
}
}
Raw
Merge Two Sorted Lists
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
if (l2 == null) {
return null;
} else {
return l2;
}
} else {
if (l2 == null) {
return l1;
} else {
boolean isL1 = true;
ListNode p = l1, q = l2;
if (l2.val < l1.val) {
p = l2;
q = l1;
isL1 = false;
}
while (p.next != null) {
while (p.next != null && p.next.val <= q.val) {
p = p.next;
}
if (p.next != null) {
ListNode qq = q;
while (qq.next != null && qq.next.val <= p.next.val) {
qq = qq.next;
}
if (qq.next == null) {
ListNode tmp = p.next;
p.next = q;
qq.next = tmp;
return isL1?l1:l2;
} else {
ListNode tmp = qq.next;
ListNode tmp2 = p.next;
p.next = q;
qq.next = tmp2;
q = tmp;
p = qq;
}
} else {
p.next = q;
return isL1?l1:l2;
}
}
p.next = q;
return isL1?l1:l2;
}
}
}
}
Raw
Remove Duplicates from Sorted Array
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int removeDuplicates(int[] A) {
if(A==null){
return 0;
}
if(A.length<2){
return A.length;
}
int p=0, q=1, len=A.length, count=0;
while(q<len){
if(A[p]==A[q]){
count++;
}else{
A[q-count] = A[q];
}
p++;
q++;
}
return q-count;
}
}
Raw
Remove Element
public class Solution {
public int removeElement(int[] A, int elem) {
int i=0, j=0;
while(j<A.length){
if(A[j]!=elem){
A[i]=A[j];
i++;
}
j++;
}
return i;
}
}
Raw
Reverse Integer
public class Solution {
public int reverse(int x) {
if(x==0) return 0;
boolean isNegative = false;
if(x<0){
isNegative = true;
}
int absX = Math.abs(x);
String str = Integer.toString(absX);
StringBuffer sb = new StringBuffer();
boolean validZero = false;
for(int i=str.length()-1;i>=0;i--){
char ch = str.charAt(i);
if(ch=='0'){
if(!validZero){
continue;
}else{
sb.append(ch);
}
}else{
validZero = true;
sb.append(ch);
}
}
try{
int rNumber = Integer.parseInt(sb.toString());
return isNegative?0-rNumber:rNumber;
}catch(NumberFormatException e){
return Integer.MAX_VALUE;
}
}
}
Raw
Reverse Words in a String
/*
Reverse Words in a String
*/
public class Solution {
public String reverseWords(String s) {
if (s==null || s.trim()=="") {
return "";
}
String[] words = s.split(" ");
StringBuffer sb = new StringBuffer();
for(int len=words.length,i=len-1;i>=0;i--){
String w = words[i].trim();
if (!w.isEmpty()) {
sb.append(w).append(" ");
}
}
return sb.toString().trim();
}
}
Raw
Same Tree
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null){
return true;
}
if((p==null && q!=null) ||(p!=null && q==null)){
return false;
}
return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
Raw
Single number
public class Solution {
public int singleNumber(int[] A) {
if(A.length==0) return 0;
if(A.length==1) return A[0];
int single = A[0];
for(int i=1,len=A.length;i<len;i++){
single^=A[i];
}
return single;
}
}
Raw
Surrounded Regions[TLE]
public class Solution {
public void solve(char[][] board) {
if(board==null || board.length==0){
return;
}
int rows = board.length;
int columns = board[0].length;
List<Pair> pairs = new ArrayList<Pair>();
for(int k=0;k<columns;k++){
if(board[0][k]=='O'){
board[0][k]='Y';
Pair p = new Pair(0,k);
pairs.add(p);
}
if(board[rows-1][k]=='O'){
board[rows-1][k]='Y';
Pair p = new Pair(rows-1,k);
pairs.add(p);
}
}
for(int k=0;k<rows;k++){
if(board[k][0]=='O'){
board[k][0]='Y';
Pair p = new Pair(k,0);
pairs.add(p);
}
if(board[k][columns-1]=='O'){
board[k][columns-1]='Y';
Pair p = new Pair(k,columns-1);
pairs.add(p);
}
}
for(int i=0;i<rows;i++){
char[] row = board[i];
for(int j=0;j<columns;j++){
char ch = row[j];
if(ch=='O'){
List<Pair> workedNodes = new ArrayList<Pair>();
if(isValid(board, i, j, workedNodes)){
if(workedNodes.size()!=0){
for(Pair p : workedNodes){
board[p.x][p.y] = 'X';
}
}
}
}
}
}
for(Pair p : pairs){
board[p.x][p.y] = 'O';
}
}
private boolean isValid(char[][] board, int r, int c, List<Pair> workedNodes){
workedNodes.add(new Pair(r,c));
List<Pair> allP = new ArrayList<Pair>();
allP.add(new Pair(r,c-1));
allP.add(new Pair(r,c+1));
allP.add(new Pair(r-1,c));
allP.add(new Pair(r+1,c));
for(Pair p : allP){
if(p.isInList(workedNodes)){
continue;
}
if(board[p.x][p.y]=='Y'){
return false;
}
if(board[p.x][p.y]=='O'){
if(!isValid(board,p.x,p.y,workedNodes)){
return false;
}
}
}
return true;
}
private static class Pair{
int x;
int y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
public boolean equals(Pair p) {
return x==p.x && y == p.y;
}
public boolean isInList(List<Pair> list){
if(list==null || list.size()==0){
return false;
}
for(Pair p : list){
if(p.equals(this)){
return true;
}
}
return false;
}
}
}
Raw
Triangle
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for(int i=triangle.size()-2;i>=0;i--){
List<Integer> l = triangle.get(i);
List<Integer> ll = triangle.get(i+1);
for(int j=0,len=l.size();j<len;j++){
int v = l.get(j);
l.set(j, v+Math.min(ll.get(j), ll.get(j+1)));
}
}
return triangle.get(0).get(0);
}
}
@steven-zou
Copy link
Copy Markdown
Author

steven-zou commented Aug 27, 2014

Some solution code for LeetCode problems

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment