【算法】解题总结：剑指Offer 29 二叉搜索树与双向链表（２种方法）、剑指Offer 29 最小的K个数（高效算法）

JZ26 二叉搜索树与双向链表

（中等）

题目

描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出或者处理，示例中输出里面的英文，比如"From left to right are:"这样的，程序会根据你的返回值自动打印输出 示例: 输入: {10,6,14,4,8,12,16} 输出:From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; 解析: 输入就是一棵二叉树，如上图，输出的时候会将这个双向链表从左到右输出，以及

从右到左输出，确保答案的正确

示例1

输入：

{10,6,14,4,8,12,16}

返回值：

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

示例2

输入：

{5,4,#,3,#,2,#,1}

返回值：

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

说明：

            5

           /

         4

        /

      3

     /

   2

  /

1

树的形状如上图

思路

方法一：

题目中，最终双向链表的结点顺序为二叉树中序遍历时的结点顺序，因此只需要用一个 ArrayList 类来存储下中序遍历的结点结果，并创建一个用于最终返回的头指针，再对 ArrayList 中的 TreeNode 结点进行双向链表的链接操作即可。

方法二：

其实还可以在中序遍历的过程中就开始构建这个双向链表，也是可以的。

下面为方法一的代码，只需微改一下便可实现方法二，这里就不再写了。

实现

public class JZ26二叉搜索树与双向链表 {

    List<TreeNode> list = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        list = new ArrayList<TreeNode>();
        inOrderTraverse(pRootOfTree);
        TreeNode head = list.get(0); //使 head 指向第一个结点
        TreeNode temp = head;
        for (int i = 1; i < list.size(); i++) {
            temp.right = list.get(i);
            temp.right.left = temp;
            temp = temp.right;
        }

        return head;
    }

    public void inOrderTraverse(TreeNode pRoot) {
        if (pRoot == null) {
            return;
        }

        inOrderTraverse(pRoot.left);
        list.add(pRoot);
        inOrderTraverse(pRoot.right);
    }
}      

JZ29 最小的K个数

（中等）

题目

描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

0 <= k <= input.length <= 10000

0 <= input[i] <= 10000

示例1

输入：

[4,5,1,6,2,7,3,8],4

返回值：

[1,2,3,4]

说明：

返回最小的4个数即可，返回[1,3,2,4]也可以

示例2

输入：

[1],0

返回值：

[]

示例3

输入：

[0,1,2,1,2],3

返回值：

[0,1,1]

思路

对于此题，我当时是设计了一个最坏时间复杂度为 Ｏ（ｎ）的算法，因此平均时间复杂度算是很高的了，比​​【官方给出的三种方法】​​理论上都要高效。另外一点，此题不必直接按排序做，那会比较低效，因为结果不必是有序序列，而且原参数数组最终也没要求有序，我们不必做多余的执行。

实现

public class JZ29最小的K个数 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();

        if (input == null || k <= 0 || k > input.length) {
            return list;
        }

        //我们限定 list 中最多只能存 k 个数
        //首先先预存入 k 个
        int i = 0;
        for (; i < k; i++) {
            list.add(input[i]);
        }
        //再决定剩余的 n - k 个数是否替换存入
        int maxIndex = 0;
        for (; i < input.length; i++) {
            maxIndex = listMaxIndex(list);
            if (list.get(maxIndex) > input[i]) { //可替换
                list.set(maxIndex, input[i]);
            }
        }
        return list;
    }

    public int listMaxIndex(List<Integer> list) {
        if (list == null) {
            return -1;
        }

        int maxIndex = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) > list.get(maxIndex)) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}