問題描述
給你一個整數陣列 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 高度平衡 二叉搜索樹，
高度平衡 二叉樹是一棵滿足「每個節點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹，
示例 1：
輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
示例 2：
輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,3] 和 [3,1] 都是高度平衡二叉搜索樹，
解題思路：
BST的中序遍歷是升序的，因此本題等同于根據中序遍歷的序列恢復二叉搜索樹，因此我們可以以升序序列中的任一個元素作為根節點，以該元素左邊的升序序列構建左子樹，以該元素右邊的升序序列構建右子樹，這樣得到的樹就是一棵二叉搜索樹，又因為本題要求平衡，那么我們可以每次選取中間元素來作為我們的根節點，這樣左右兩棵子樹的高度差值就小于等于1，而一直遞回執行這樣的程序，最終就可以得到一個高度平衡的二叉排序樹，
注意：這里其實也用到了折半查找判定樹的思路，折半查找每次將待查找的關鍵字與中間元素的值作比較，如果小于的話，就往中間元素左邊查找，否則，往右邊查找，這樣，折半查找的程序其實可以用二叉樹來描述，這個二叉樹是高度平衡的二叉排序樹
實作代碼
class Solution {
public int [] arr; //保存原有序陣列，避免陣列傳參
public TreeNode genBinaryTree(int low,int high){
//如果low>high,就沒有元素，直接回傳空即可
if(low>high){
return null;
}
//如果low==high，待處理序列只有一個元素，這個結點將被作為葉子結點，回傳即可
if(low==high){
TreeNode p=new TreeNode(arr[low]);
p.left=null;
p.right=null;
return p;
}
//否則，找到中間元素，然后構造根節點，然后繼續完善該結點的左右子樹
int mid=(low+high+1)/2;
TreeNode p=new TreeNode(arr[mid]);
p.left=genBinaryTree(low,mid-1);
p.right=genBinaryTree(mid+1,high);
return p;
}
public TreeNode sortedArrayToBST(int[] nums) {
int len=nums.length;
arr=new int[len];
for(int i=0;i<len;i++){
arr[i]=nums[i];
}
return genBinaryTree(0,len-1);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/262570.html
標籤：其他
下一篇：VSCode超實用插件