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

文章预览

最小高度树

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

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

      0 
     / \ 
   -3   9 
   /   / 
 -10  5 





    

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

• 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

• 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

• 1
• 2
• 3
• 4
• 5

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

加油！

共同努力！

Keafmd

………………………………