每日一道 LeetCode (24)：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
題目來(lái)源：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹(shù)。
本題中，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)?的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。
示例:
給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個(gè)高度平衡二叉搜索樹(shù)：
??????0
?????/?\
???-3???9
???/???/
?-10??5
解題思路
啥子玩意？還能通過(guò)一個(gè)數(shù)組逆推一個(gè)二叉樹(shù)出來(lái)？這題出的還敢再 BT 點(diǎn)不。
絕對(duì)是神仙思路，玩不轉(zhuǎn)玩不轉(zhuǎn)，直接投降翻答案。
最開(kāi)始，需要明確一件事兒，啥是二叉搜索樹(shù)？
二叉搜索的顯著特點(diǎn)：
對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn) X ，它的左子樹(shù)中所有關(guān)鍵字值小于 X 的關(guān)鍵字值，而它的右子樹(shù)中所有關(guān)鍵字值大于 X 的關(guān)鍵字值。
簡(jiǎn)單來(lái)講就是 左 < 根 < 右。
根據(jù)這個(gè)特性就有了，如果一個(gè)二叉搜索樹(shù)做中序遍歷，那么會(huì)得到一個(gè)遞增的序列。
放到這道題里，就很明確了，這道題給出的數(shù)組序列實(shí)際上是一個(gè)中序遍歷的二叉搜索樹(shù)。
官方的題解中，有幾個(gè)問(wèn)題比較好，我摘錄過(guò)來(lái)（以下內(nèi)容來(lái)源官方題解）。
給定二叉搜索樹(shù)的中序遍歷，是否可以唯一地確定二叉搜索樹(shù)？答案是否定的。如果沒(méi)有要求二叉搜索樹(shù)的高度平衡，則任何一個(gè)數(shù)字都可以作為二叉搜索樹(shù)的根節(jié)點(diǎn)，因此可能的二叉搜索樹(shù)有多個(gè)。
如果增加一個(gè)限制條件，即要求二叉搜索樹(shù)的高度平衡，是否可以唯一地確定二叉搜索樹(shù)？答案仍然是否定的。
直觀地看，我們可以選擇中間數(shù)字作為二叉搜索樹(shù)的根節(jié)點(diǎn)，這樣分給左右子樹(shù)的數(shù)字個(gè)數(shù)相同或只相差 11，可以使得樹(shù)保持平衡。如果數(shù)組長(zhǎng)度是奇數(shù)，則根節(jié)點(diǎn)的選擇是唯一的，如果數(shù)組長(zhǎng)度是偶數(shù)，則可以選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)或者選擇中間位置右邊的數(shù)字作為根節(jié)點(diǎn)，選擇不同的數(shù)字作為根節(jié)點(diǎn)則創(chuàng)建的平衡二叉搜索樹(shù)也是不同的。
到這一步，官方的題解已經(jīng)把最艱難的部分解決了 「如何確定一個(gè)根節(jié)點(diǎn)」 。
下一步需要做的是把其余的數(shù)字放在二叉樹(shù)的左右子樹(shù)里面。
那么如何放呢？很簡(jiǎn)單，我們重復(fù)剛才的過(guò)程，比如左子樹(shù)，先找到左子樹(shù)的根節(jié)點(diǎn)（中間的那個(gè)數(shù)），然后遞歸這個(gè)過(guò)程。
我只畫(huà)了兩次迭代，完整的畫(huà)完這個(gè)圖太大了， PPT 畫(huà)不下。
官方題解上給出來(lái)三種解法，一種是選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)，另一種是選擇中間位置右邊的數(shù)字作為根節(jié)點(diǎn)，最后一種是把前兩種結(jié)合起來(lái)。
解題方案一：中序遍歷，選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)
選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)，則根節(jié)點(diǎn)的下標(biāo)為 mid = (left + right) / 2，此處的除法為整數(shù)除法。
public?TreeNode?sortedArrayToBST(int[]?nums)?{
????return?helper(nums,?0,?nums.length?-?1);
}
//?中序遍歷，選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)
public?TreeNode?helper(int[]?nums,?int?left,?int?right)?{
????if?(left?>?right)?return?null;
????int?mid?=?(left?+?right)?/?2;
????TreeNode?node?=?new?TreeNode(nums[mid]);
????node.left?=?helper(nums,?left,?mid?-?1);
????node.right?=?helper(nums,?mid?+?1,?right);
????return?node;
}
解題方案二：中序遍歷，選擇中間位置右邊的數(shù)字作為根節(jié)點(diǎn)
有了上面這個(gè)方案一，再寫(xiě)這個(gè)就已經(jīng)很簡(jiǎn)單了，在這個(gè)方案中，根節(jié)點(diǎn)的計(jì)算公式為 mid = (left + right + 1) / 2 。
//?中序遍歷，選擇中間位置右邊的數(shù)字作為根節(jié)點(diǎn)
public?TreeNode?helper_1(int[]?nums,?int?left,?int?right)?{
????if?(left?>?right)?return?null;
????int?mid?=?(left?+?right?+?1)?/?2;
????TreeNode?node?=?new?TreeNode(nums[mid]);
????node.left?=?helper(nums,?left,?mid?-?1);
????node.right?=?helper(nums,?mid?+?1,?right);
????return?node;
}
實(shí)際上有變化就只有 mid 的取值，剩下啥都沒(méi)變。
解題方案三：中序遍歷，選擇任意一個(gè)中間位置數(shù)字作為根節(jié)點(diǎn)
這個(gè)方案的 mid 取值就很有意思了，先不看后面，各位可以先思考下如何任意的取一個(gè)中間位置。
也就是在 mid = (left + right) / 2 和 mid = (left + right + 1) / 2 之間取一個(gè)值。
官方的示例圖我先放出來(lái)，別急著往下翻：
結(jié)果是可以取一個(gè)隨機(jī)數(shù)：mid = (left + right + new Random().nextInt(2)) / 2 。
//?中序遍歷，選擇任意一個(gè)中間位置數(shù)字作為根節(jié)點(diǎn)
public?TreeNode?helper_2(int[]?nums,?int?left,?int?right)?{
????if?(left?>?right)?return?null;
????int?mid?=?(left?+?right?+?new?Random().nextInt(2))?/?2;
????TreeNode?node?=?new?TreeNode(nums[mid]);
????node.left?=?helper(nums,?left,?mid?-?1);
????node.right?=?helper(nums,?mid?+?1,?right);
????return?node;
}
這個(gè)方案三的思路確實(shí)很清奇，有點(diǎn)意思。
今天這道題需要通過(guò)一個(gè)數(shù)組逆推出來(lái)一個(gè)二叉搜索樹(shù)，咳咳，第一次見(jiàn)確實(shí)不會(huì)做，就當(dāng)背答案了。
