最小高度树Java版本（力扣）

最小高度树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

 0 / \ -3   9 /   / 
 -10  5 

  

 

  
1
  
2
  
3
  
4
  
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; }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

完整代码（含测试代码）：

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; }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

输出结果：

0
-3
9

Process finished with exit code 0

  

 

  
1
  
2
  
3
  
4
  
5
 

看完如果对你有帮助，感谢点赞支持！
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它[哈哈]

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/112121618