[CSE] 10.22

1. 
Two binary trees are identical, if the data in each of the corresponding node are the same and the structures of them are the same.
Develop an algorithm to determine whether two binary tree are identical.

2. 
Given two sorted array (ascending order), find the median of them.
For example, the median of [1, 4, 5, 7] and [2, 3, 8, 9] is 4.5
NOTE: Your algorithm MUST less than O(M + N) where M and N is the lenghths of the two sorted array. A simple merge sort is too slow for this problem. (Imagine how slow it would be if there are 2 billion data, and you need to loop over 1 billion elements.)

[Solution1].java

public class Solution{
    public boolean isSame(Node a, Node b){
        if(a == null && b == null) return true;
        else if(a == null || b == null) return false;
        else{
            return a.val == b.val && isSame(a.left, b.left) &&
                isSame(a.right && b.right);
        }
    }
}

[Solution2].java

/**
 * We could use constance time to decide whether a point is middle one or not,
 * so I did binary search for each array to find the middle point.
 * BTW, I have not return the median, just middle or left middle point... lazy... TC log(n*m)
 */
 
public class Solution{
    public int findMedian(int[] a, int[] b){
        int totalL = a.length + b.length;
        int half = (totalL % 2 == 0)? totalL / 2 - 1: totalL / 2;
    	if(totalL == 0) return -1;
    	else if(a.length == 0) return b[half];
    	else if(b.length == 0) return a[half];
    	
        Result result = isMiddle(a, b, half);
        if(result == null) result = isMiddle(b, a, half);
        return result.val;
        
    }
    
    public Result isMiddle(int[] a, int[] b, int half){
        int begin = 0, end = a.length - 1;
        int middle = (end - begin) / 2;
        while(begin <= end){
            if(half < middle){
                end = middle - 1;
                middle = (begin + end) / 2;
            }
            else if(half == middle){
                if(a[middle] <= b[0]) return new Result(a[middle]);
                else{
                    end = middle - 1;
                    middle = (begin + end) / 2;
                }
            }
            else{
            	if(half - middle > b.length){
            		end = middle - 1;
            		middle = (begin + end) / 2;
            	}
            	else if (half - middle == b.length){
            		if(a[middle] >= b[half - middle - 1]) return new Result(a[middle]);
            		else{
            			begin = middle + 1;
            			middle = (begin + end) / 2;
            		}
            	}
            	else{
            		if(a[middle] >= b[half - middle - 1]){
                        if(a[middle] <= b[half - middle]) return new Result(a[middle]);
                        else{
                            end = middle - 1;
                            middle = (begin + end) / 2;
                        }
            		}
            		else{
            			begin = middle + 1;
            			middle = (begin + end) / 2;
            		}
            	}
            }
        }
        return null;
    }
    
    class Result{
    	int val;
    	Result(int val){
    		this.val = val;
    	}
    }
}