Daily Archives: September 14, 2014

Leetcode: Merge Sorted Array

Posted on by
Reply

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

public class Solution {
 public void merge(int A[], int m, int B[], int n) {
   int index = m+n-1;
   while(index>=0 && m>0 && n>0){
     if(A[m-1]>=B[n-1]){
       A[index]=A[m-1];
       m--;
     }else{
       A[index]=B[n-1];
       n--;
     }
     index--;
   }
   if(n>0){
     for(int i=0;i<n;i++){
       A[i]=B[i];
     }
   }
 }
}

 

 

FacebookTwitterGoogle+Share

Leetcode: Symmetric Tree

Posted on by
Reply

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Recursive:

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

 

Non-Recursive/Iteratively:



 


					

		
		
	


				
					
	

		

						
Leetcode: Convert Sorted Array to Binary Search Tree

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.


public class Solution {
 public TreeNode sortedArrayToBST(int[] num) {
   return sortedArrayToBST(num, 0, num.length-1);
 }
 
 public TreeNode sortedArrayToBST(int[] num, int start, int end){
   if(start>end){
     return null;
   }
   int pivot = (start+end)/2;
   TreeNode root = new TreeNode(num[pivot]);
   root.left = sortedArrayToBST(num, start, pivot-1);
   root.right = sortedArrayToBST(num, pivot+1, end);
   return root;
 }
}


 


					

		
		
	


				
					
	

		

						
Leetcode: Balanced Binary Tree

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			
Given a binary tree, determine if it is height-balanced.


For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.


public class Solution {
 public boolean isBalanced(TreeNode root) {
   return getRebalancedHeight(root)==-1?false:true;
 }
 //getHeight for each node, -1 if it is already not balanced.
 public int getRebalancedHeight(TreeNode root){
 if(root==null){
   return 0;
 }
 int leftHeight = getRebalancedHeight(root.left);
 int rightHeight = getRebalancedHeight(root.right);
 if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
   return -1;
 }
   return Math.max(leftHeight, rightHeight)+1;
 }
}