【算法】解題總結：劍指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;
    }
}