廣州技術(shù)支持 網(wǎng)站建設(shè)清遠(yuǎn)疫情防控措施
108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
分析
給定一個有序數(shù)組，要求轉(zhuǎn)換為二叉搜索樹。
數(shù)組是有序的，并且要求二叉樹。
這里看到數(shù)組是有序的，馬上想到二分，但是又不需要完全二分 實(shí)現(xiàn)。
再復(fù)習(xí)二叉搜索樹的結(jié)構(gòu)特點(diǎn)：
左邊節(jié)點(diǎn)的值 < 中間節(jié)點(diǎn)的值
left < mid
中間節(jié)點(diǎn)的值 < 右節(jié)點(diǎn)的值
mid < right
看到這種情況，可以讓計(jì)算機(jī)來幫助我們處理左右半邊的節(jié)點(diǎn)。
于是，我們可以用遞歸來進(jìn)行處理。
遞歸
-
先遞歸找到中間節(jié)點(diǎn)mid的下標(biāo)
即mid = left + right >> 1 -
再將
root指向nums[mid] -
接著遞歸處理左半邊
即root.left = fun(nums , left , mid - 1) -
再遞歸處理右半邊
即root.right = fun(nums , mid + 1 , right)
這里很多小伙伴會疑惑為什么這樣就可以AC，因?yàn)檫f歸到最后的基元情況都是只有一個節(jié)點(diǎn)即根節(jié)點(diǎn)，不過是依次每次處理好每一層的根節(jié)點(diǎn)罷了。
注意
遞歸要對邊界條件進(jìn)行判斷處理
當(dāng)數(shù)組下界下標(biāo)大于數(shù)組上界下標(biāo)時(shí)，返回空，這種情況非法。
ACcode
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
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;}int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums , left , mid - 1);root.right = helper(nums , mid + 1 ,right);return root;}
}
喜歡的小伙伴點(diǎn)點(diǎn)關(guān)注，我們下期再見??