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