public class Solution{
    public int binarySearch(int[] nums, int target){
        if(nums == null && nums.length == 0)return -1;

        int start = 0;
        int end = nums.length - 1;
        int mid;

        while(start + 1 < end){
            mid = start + (end - start) / 2;
            if(nums[mid] > target){
                end = mid;
            }else if(nums[mid] < target){
                start = mid;
            }else{
                end = mid;
            }
        }

        if(nums[start] == target){
            return start;
        }
        if(nums[end] == target){
            return end;
        }

        return -1;
    }
}

public class Solution{
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
        ArrayList result = new ArrayList();

        if(root == null){
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for(int i = 0; i < size; i++) {
              TreeNode head = queue.poll();
              level.add(head.val);
              if(head.left != null){
                  queue.offer(head.left);
              }
              if(head.right != null){
                  queue.offer(head.right);
              }
            }
            result.add(level);
        }

    }
}

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
    }
}

public class Solution{
    public ResultType traversal(TreeNode root){
        // null or left
        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;
    }
}

public class Solution {


    //模板
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        traversal(root, result);
        return result;
    }


    public void traversal(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }
        //do sth with the root(eg:print  visit  result.add(root.val);)  前序这一行
        traversal(root.left, result);
        //do sth with the root(eg:print  visit  result.add(root.val);) 中序在一样
        traversal(root.right, result);
        //do sth with the root(eg:print  visit  result.add(root.val);)  后序在者一样
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
//DP的题型在leetcode里一共有几种
//1.矩阵DP matrix（eg 机器人左上到右下 triangle）
//2. 1维DP sequence （eg word break ， jump game）
//3. 2维DP 2sequence （eg edit distan等把A词变成B词的）
//4. Interval (eg merge interval, insert interval)
//
//所以 这几类题 要怎么做呢
//1. status  
// Matrix      : f[i][j] 从1,1走到i,j ...
// Sequence    : f[i] 前i个 ***
// 2 Sequences : f[i][j] word1前i个匹配上word前j个 *** 
// Interval    : f[i][j] 表示区间i-j ***

//2.Transfer  DP 推导过程
//LCS: f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1)  longest common sequence
// LIS: f[i] = max(f[j] + 1, a[i] >= a[j])   longest increasing sequence
// 分析最后一次划分/最后一个字符/最后***

//3. initialize  初始状态
// f[i][0] f[0][i]
// f[0]
// LIS: f[1..n] = 1;

//4. answer  
// LIS: max{f[i]}
// LCS: f[n][m]


//5. loop   
// Interval: 区间从小到大，先枚举区间长度. Palindrome Patitioning II 



}

public class Solution {

    public ArrayList<Integer> permute(int[] num){
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path=new ArrayList<Integer>();
        permuteHelper(results,path,num/*?*/);
        return results;
    }


    private void permuteHelper(ArrayList<ArrayList<Integer>> results,ArrayList<Integer> path,int[] num){
        if(path.size()==num.length){ //是方法结束的条件
            results.add(new ArrayList<Integer>(path));
            return;
        }
        for(int =/*?*/;i<numm.length;i++){
            //提议要求要跳过那些条件
            path.add(num[i]);
            permuteHelper(results, path, num);
         path.remove(path.size()-1);
        }
    }
}

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k * 2 + 1 < A.length) {
            int son = k * 2 + 1;
            if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])
                son = k * 2 + 2;
            if (A[son] >= A[k])
                break;

            int temp = A[son];
            A[son] = A[k];
            A[k] = temp;
            k = son;
        }
    }

    public void heapify(int[] A) {
        for (int i = (A.length - 1) / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }
}

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k < A.length) {
            int smallest = k;
            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
                smallest = k * 2 + 1;
            }
            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
                smallest = k * 2 + 2;
            }
            if (smallest == k) {
                break;
            }
            int temp = A[smallest];
            A[smallest] = A[k];
            A[k] = temp;

            k = smallest;
        }
    }

    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        } // for
    }
}

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftup(int[] A, int k) {
        while (k != 0) {
            int father = (k - 1) / 2;
            if (A[k] > A[father]) {
                break;
            }
            int temp = A[k];
            A[k] = A[father];
            A[father] = temp;

            k = father;
        }
    }

    public void heapify(int[] A) {
        for (int i = 0; i < A.length; i++) {
            siftup(A, i);
        }
    }
}