最小高度樹
給定一個有序整數陣列，元素各不相同且按升序排列，撰寫一個演算法，創建一棵高度最小的二叉搜索樹，
示例:
給定有序陣列: [-10,-3,0,5,9],
一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：
0
/ \
-3 9
/ /
-10 5
題意：讓我們根據給的有序陣列，創建一個高度最小的二叉樹，
思路：遞回求解，sortedArrayToBST方法中傳入的陣列，我們取陣列的中間值為根節點，然后將陣列的左半部分傳入sortedArrayToBST方法，這樣回傳的就是左子樹的根節點，賦值給node.left ；將陣列的右半部分傳入sortedArrayToBST方法，這樣回傳的就是右子樹的根節點，賦值給node.right ，就這樣一直遞回下去，最后機就構建成了一棵高度最小的二叉搜索樹，
正確代碼：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0)
return null;
TreeNode node = new TreeNode(nums[nums.length/2]);
node.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));
node.right = sortedArrayToBST(Arrays.copyOfRange(nums,nums.length/2+1,nums.length));
return node;
}
}
完整代碼（含測驗代碼）：
package com.Keafmd.day0102;
import java.util.Arrays;
/**
* Keafmd
*
* @ClassName: MinimumHeightTree
* @Description: 最小高度樹
* @author: 牛哄哄的柯南
* @date: 2021-01-02 19:29
*/
public class MinimumHeightTree {
public static void main(String[] args) {
Solution01022 solution01022 = new Solution01022();
int []nums={-10,-3,0,5,9};
TreeNode result = solution01022.sortedArrayToBST(nums);
System.out.println(result.val);
System.out.println(result.left.val);
System.out.println(result.right.val);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution01022 {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0)
return null;
TreeNode node = new TreeNode(nums[nums.length/2]);
node.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));
node.right = sortedArrayToBST(Arrays.copyOfRange(nums,nums.length/2+1,nums.length));
return node;
}
}
輸出結果：
0
-3
9
Process finished with exit code 0
看完如果對你有幫助，感謝點贊支持！
如果你是電腦端，看到右下角的 “一鍵三連” 了嗎，沒錯點它[哈哈]
加油！
共同努力！
Keafmd
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243815.html
標籤：java