本文为牛客网上66道剑指offer题解

1. 二叉树与双向链表

本题就是二叉树中序遍历的变化，需要熟悉中序遍历非递归的写法，另外注意：
注意pre和p一前一后走，注意第一个节点head的处理：即整个二叉树中最左边的节点。 
import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode root) {
        if (root == null)
            return null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode head = new TreeNode(0);
        TreeNode pre = null;
        boolean isFirst = true;
        while(p != null || !s.isEmpty()){
            while(p != null){
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            if (isFirst){
                head = p; //注意第一个节点head的处理 pre = p;
                isFirst = false;
            }
            else{
                pre.right = p;
                p.left = pre;
                pre = p;
            }
            p = p.right;
        }
        return head;
    }
}

2. 最小的K个数

本题最好的解法就是堆排序，借助本题把堆排序搞清楚。
堆排序就是一个for循环（i从大到小）里面加个调整堆操作，然后交换i和头。 

	import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(input == null || input.length == 0 || k < 0 || k > input.length)
            return res;
        for (int i = input.length - 1; i > input.length - 1 - k; i -- ){
            min_heapify(input, i);
            swap(input, i, 0);
        }
        for(int i = input.length - 1; i > input.length - 1 - k; i--)
            res.add(input[i]);
        return res;
    }
    private void min_heapify(int[] input, int n){
        int child = 0;
        for(int i = (n - 1)/2; i >= 0; i--){
            child = i*2 + 1;
            if (child < n && input[child] > input[child + 1])
                child ++;
            if (input[child] < input[i])
                swap(input, i, child);
        }
    }
    private void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
基于快排的版本： 
import java.util.ArrayList;
public class Solution {
    private int K = 0;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (input == null || input.length == 0 || k < 0 || k > input.length)
            return res;
        K = k;
        QuickSort(input, 0, input.length - 1);
        for(int i = input.length - 1; i >= input.length -K ;i--)
            res.add(input[i]);
        //for(int i: input)
            //System.out.println(i);
        return res;
    }
    private void QuickSort(int[] A, int l, int r){
        if (l >= r)
            return;
        int i = l, j = r;
        int tmp = A[i];
        while(i< j){
            while(i < j && A[j] < tmp)
                j--;
            A[i] = A[j];
            while(i < j && A[i] > tmp)
                i++;
            A[j] = A[i];
        }
        A[i] = tmp;
        if(A.length - i >= K)                //如果后面K个已经有序，提前返回即可
            return;
        QuickSort(A, l, i - 1);
        QuickSort(A, i+1, r);
    }
}