【Go 刷 LeetCode】一棵樹引發(fā)的算法題...

點擊上方藍字關注加小星星?

濤哥給你我所有~

今天為大家講解 LeetCode 第 108 題，是一道簡單難度的題目。

題目描述

將一個按照升序排列的有序數(shù)組，轉換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

示例:

給定有序數(shù)組: [-10,-3,0,5,9],

一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：

??????0
?????/?\
???-3???9
???/???/
?-10??5

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree 著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路

這里，如果我們知道二叉樹的中序遍歷就是升序序列的話，那這道題就比較清晰了。（二叉樹是一種很重要的數(shù)據(jù)結構，不了解的朋友自行去學習一下哦：）

選擇中間位置左邊的數(shù)字作為根節(jié)點，則根節(jié)點的下標 mid = (left + right) / 2。

樹結構多用遞歸實現(xiàn)。

代碼實現(xiàn)

//?go
//Definition?for?a?binary?tree?node.
type?TreeNode?struct?{
?Val???int
?Left??*TreeNode
?Right?*TreeNode
}

func?sortedArrayToBST(nums?[]int)?*TreeNode?{
?return?helper(nums,?0,?len(nums)-1)
}

func?helper(nums?[]int,?left?int,?right?int)?*TreeNode?{
?if?left?>?right?{
??return?nil
?}
?mid?:=?(left?+?right)?>>?1?//?等同于(left?+?right)?/?2，位運算效率較高
??//?注意：go 中的位運算符優(yōu)先級高于加減，必須帶括號！
?root?:=?&TreeNode{Val:?nums[mid]}
?root.Left?=?helper(nums,?left,?mid-1)
?root.Right?=?helper(nums,?mid+1,?right)
?return?root
}

//?java
class?Solution?{
????public?TreeNode?sortedArrayToBST(int[]?nums)?{
????????return?helper(nums,?0,?nums.length?-?1);
????}

????public?TreeNode?helper(int[]?nums,?int?left,?int?right)?{
????????if?(left?>?right)?{
????????????return?null;
????????}

????????//?總是選擇中間位置左邊的數(shù)字作為根節(jié)點
????????int?mid?=?left?+?right?>>?1;?//?Java?中的位運算符優(yōu)先級低于加減，可以不帶括號

????????TreeNode?root?=?new?TreeNode(nums[mid]);
????????root.left?=?helper(nums,?left,?mid?-?1);
????????root.right?=?helper(nums,?mid?+?1,?right);
????????return?root;
????}
}

這里另外多說一點，有個小坑。就是 Go 中的運算符優(yōu)先級和其他語言（如我所知的Java，C）有不一樣，搞不懂 Go 這里搞啥特殊，真是坑

這里順便給出 Go 和 Java 的運算符優(yōu)先級表

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～

推薦閱讀

• 【算法 Go 實現(xiàn)】區(qū)域和檢索 - 數(shù)組可修改
  

---

喜歡本文的朋友，歡迎關注“Go語言中文網(wǎng)”：

Go語言中文網(wǎng)啟用微信學習交流群，歡迎加微信：274768166，投稿亦歡迎