Minimum Height Tree Java Version (Force button)

Minimum height tree

Given an ordered array of integers with different elements arranged in ascending order, write an algorithm to create a binary search tree with the smallest height.

Example:

Given an ordered array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10, NULL,5], which could represent the following highly balanced binary search tree:

      0 
     / \ 
   -3   9 
   /   / 
 -10  5 
Copy the code

Let’s create a minimum height binary tree from the ordered array given.

SortedArrayToBST method in the array, we take the middle value of the array as the root node, and then pass the left half of the array into the sortedArrayToBST method, so the return is the root node of the left subtree, assigned to node.left; Pass the right half of the array into the sortedArrayToBST method, which returns the root node of the right subtree, assigns the value to Node. right, and so on recursively until the machine builds a binary search tree with the smallest height.

Correct code:

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));
        returnnode; }}Copy the code

Complete code (including test code) :

package com.Keafmd.day0102;

import java.util.Arrays;

/**
 * Keafmd
 *
 * @ClassName: MinimumHeightTree
 * @Description: minimum height tree *@author: Conan the cow@date: 2021-01-02 do * /
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(intx) { 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));
        returnnode; }}Copy the code

Output result:

0
-3
9

Process finished with exit code 0
Copy the code

If it helps you, thank you for your support!

If you’re on the computer side, see the”Three even a key“Yeah, click on it.”



Come on!

Work together!

Keafmd