“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

preface

The ordered array is converted into a binary search tree as shown below:

Given an array of integers, numS, whose elements are sorted in ascending order, convert it into a highly balanced binary search tree.

A highly balanced binary tree is one that satisfies the requirement that the absolute value of the height difference between the left and right subtrees of each node is no more than 1.

Example 1:

Input: nums = [-, 10-3,0,5,9] output: [0, 3, 9, 10, null, 5] : [0, 10, 5, null, 3, null, 9] also will be deemed to be the correct answer:Copy the code

A, thinking

The title is short, so we can sort out the key information in the title first

  • Input: ascending one-dimensional array (no repeating elements)
  • Output: highly balanced binary search number

In a binary search tree, the left subtrees are smaller than the root node, and the right subtrees are larger than the root node (if the left and right subtrees are not empty)

In the case of the ascending array nums = [-10,-3,0,5,9] in Example 1, there are many kinds of binary search trees it can form. Here’s one possibility:

But for node 0, the depth of the left subtree is 2 and the depth of the right subtree is 0, the difference is more than 1 (for the root node, the height difference between the left and right subtrees is also more than 1). Then the binary search tree cannot construct a highly balanced binary search tree.

What if the height difference between the left and right subtrees is no more than 1?

It’s very simple. We just use a dichotomy and take the element in the middle of the array as the root node. The node to the left of the root node is the left subtree, and the node to the right of the root node is the right subtree.

To sum up, the general steps of recursion are divided into the following three steps:

Left = 0, right = n

  1. mid = (left+right)/2And willnums[mid]Set it to the root node
  2. will0 ~ mid -1Think of it as a left subtree
  3. willmid ~ rightThink of it as the right subtree

Note: in recursion we need to set the boundary cases correctly. If left > right, there are no available elements in the array.

Second, the implementation

The implementation code

The implementation code is consistent with the idea, and using recursion makes the code look a little cleaner.

    /** * highly balanced binary tree */
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length-1);
    }

    public TreeNode dfs(int[] nums, int left, int right){
        if (left > right)
            return null;
        int mid = (left+right)/2;  // take the middle value
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, left, mid-1);
        root.right = dfs(nums, mid+1, right);
        return root;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {-10, -3.0.5.9};
        TreeNode treeNode = new Number108().sortedArrayToBST(nums);
        System.out.println("debug");
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section