Lintcode--Binary Tree preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new LinkedList<Integer>();
    if (root == null) return ans; //recursive 
    Stack<TreeNode> stack = new Stack<TreeNode>(); //using stack LIFO
    

stack.push(root);
    

while (!stack.isEmpty()) {
        TreeNode cur = stack.pop(); using pop to get the value of root of first
        ans.add(cur.val);
        // should it do reversely, right?
        if (cur.right != null) stack.push(cur.right);
        if (cur.left != null) stack.push(cur.left); //Last in First Out 
    }
    return ans;
}

Binary Tree: 

Preorder Traversal: DLR

Inorder Traversal: LDR

Post Order Traversal: RLD

LintCode Merge Two Sorted Arraylist

public static ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
               //null check
if (A == null && B == null) {
return new ArrayList<Integer>(Arrays.asList(-1));
} else if (A == null && B != null) {
return B;
} else if (A != null && B == null) {
return A;
}
             
               // initial a new array
ArrayList<Integer> result = new ArrayList<Integer>();

               
for (int i = 0,j=0; i <A.size() || j <B.size() ;) {

if (i < A.size() && j > B.size()-1) {
result.add(A.get(i));i++;continue;
} else if (i > A.size()-1 && j < B.size()) {
result.add(B.get(j));j++;continue;
}

if (A.get(i) < B.get(j)) {
result.add(A.get(i));i++;
} else if (A.get(i) > B.get(j)) {
result.add(B.get(j)); j++;
} else if (A.get(i) == B.get(j)) {
result.add(A.get(i));
result.add(B.get(j));
i++;
j++;
}
}

return result;
    }

一开始不明白的点：
（1）  i <A.size() || j <B.size() 应该选OR 做，如果是选择&& 的话，T &F return F 所以就会跳出循环，这里应该使用OR, T V F= return True 只有在F V F 的时候才return false (boolean 值）
（2） 结束 语句：

if (i < A.size() && j > B.size()-1) {
result.add(A.get(i));i++;continue;
} else if (i > A.size()-1 && j < B.size()) {
result.add(B.get(j));j++;continue;
}
这句是为了判断当A和B长度不一致的时候应该怎样处理， 如果A 比B 长，那么我们就填入B的元素。如果B比A长，那么我们就应该填入B剩下的元素。
(3) break 和continue 均是跳出循环的，例如break ，就直接return 了，continue 就直接回到for loop 或者while.
(4) 一开始只想用一个指针，就是result 的指针。但是在比较当中，最好用两个指针。
(5) 这个和reomove duplicate from sorted array 都是很相似的做法，都是使用两个指针，并且都是比较i和j的位置。

binary tree/ binary search tree

Binary Tree Template:
二叉树：

（1）Preorder
（2）Inorder
（3） Post order

Traversal

Template 1: Traverse

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}


Tempate 2: Divide & Conquer

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }
        
        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);
        
        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}

Stack and Queue: 

(1) Queue: FIFO 

(2) Stack: LIFO  

二分法binary search 模板

二分法模板：
二分法的主要特点：
（1） 每次都要砍一半（所以很快）时间复杂度是O(logN)
（2）如果array 是没有排序的，那首先必须得排序，二分法是基于排序的基础上来做的。

需要注意的特点：
（1）异常值处理：数组的长度为0，target value 分别在第一位和末尾找到。
（2）注意start+1< end 防止死循环
 （3）mid = start + (end-start)/2

Both your formulas will overflow, but under different circumstances:

• The (start+end) part of your (start+end)/2 formula will overflow when start and end are both close to the integer limit on the same side of the range (i.e. both positive or both negative).
• The (end-start) part of your start+(end-start)/2 formula will overflow when start is positive and end is negative, and both values are close to the respective ends of the representable integer values.

There are no "generic" rules, you do it case-by-case: look at parts of your formula, think of situations that could cause overflow, and come up with ways to avoid it. For example, the start+(end-start)/2 formula can be shown to avoid overflow when you average values with the same sign.

This is the hard way; the easy way is to use higher-capacity representations for intermediate results. For example, if you use long longinstead of int to do intermediate calculations and copy the results back to int only when you are done, you will avoid overflow assuming that the end result fits in an int.

int binarySearch(vector<int> &A, int target) {
        //如果Array的size是0直接return -1
if (A.size() == 0) {
            return -1;
        }
       
//赋值
        int start = 0;
        int end = A.size() - 1;
        int mid;

        while (start + 1 < end) { //注意点一： 防止死循环          
            mid = start + (end - start) / 2; //注意点二：防止溢出， 如果使用 [(end+start)/2]，如果size 是10的话，5+7=12> 10 中值数就会大于原有的规定，所以就会溢出。 这种方法
                                //是会防止溢出
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }
     
//如果一开始就相等，就直接return
        if (A[start] == target) {
            return start;
        } //先判断开始和最后一位是否相等，特殊值处理。
        if (A[end] == target) {
            return end;
        }

        return -1;
    }
};

一些题目的变体：
1. Search for a Range:
http://lintcode.com/en/problem/search-for-a-range/

用二分法模板：可以在初次二分法之后，

（1）先向左边找期初值
（2）再像右边找最后的一个值。

2. Search in a sorted matrix:
使用两次binary search 方式，先对列进行搜索再对行进行搜索。

3. Search in a sorted matrix II:
 http://lintcode.com/en/problem/search-a-2d-matrix-ii/

和sorted matrix 不一样的地方：

substring and subset method 九章算法

Subtring 现在发展了很多方法但是常用的都是那几种:

(1) Brute Force （暴力破解法）：
      时间复杂度：
     普通 ~NM
     如果souce == target 长度的话，那就是 N(N-M+1)

(2) KMP 算法: 
     时间复杂度： O(M+N)

(3) Boyer-Moore 算法:
     时间复杂度：O(1)


Brute Force 算法设计： 
正所谓暴力破解，那就是逐个对应的关系了。

source : A B A B A
target:   A B A

（1） 首先我们将target 的第一位逐个对应。如果第一位不符合的话，那么将target 的第一位移动到第二位。如此类推。
（2）如果是第一位符合的话，我们就继续用target 对应source 的第二位，第三位，知道target 的长度用完。

如果我们首先思考如果我们都写成两个for loop的话，那么会出现什么问题呢？
那就是当我们每遍历一个source的时候，我们都要遍历完target. 另外会出现溢出的情况。例如source 长度为10，target 长度为3，当指针到了9的时候，指针就会指出source 之外，这里会出现溢出的情况。 

那么我们再考虑两个指针：
进入一个for loop 之后， 我们不需要遍历每个target,只要是第一个target 不相等，我们就可以跳出target循环，然后进入+1的source 循环，那么这里我们这里可以考虑的是判断类语句：
（例如while 和if )

然后最后的条件当target 长度用完，那就是找到字符串。

图（1）

所以我们可以写成：
    public int strStr(String source, String target) {
        //write your code here
        //异常值处理
        if(source == null || target == null ) {
return -1;
}

int n = source.length();
int m = target.length();

for (int i = 0; i <= n - m; i++) {
int j;

                        for(j=0; j < m ; j++) {
if(source.charAt(i + j) != target.charAt(j)) {break;}
}
if (j == m) {
return i;
}
}
        return -1;
    }
}

KMP 算法：
source: BBC ABCDAB ABCDABCDABDE
target:  ABCDABD

(1) 在source 找出第一个匹配的字母。
(2) target+1 进行匹配
(3) 如果不匹配我们就使用这个公式进行移位：
     移动的位置= target 字符算已经移动的位置 - target 字符的部分匹配值，

好像这个字符算： ABCDABD, 我们有AB是相等的，所以部分匹配值为AB（2），这个部分匹配值实在已经移动的字符串的基础上。

所以上面移动了三个位置，但是并没有部分配置值。所以是2-0=2，移动两位。 

Boyer-Moore 算法： 

逆向思维法：

Subsets: