This is the 12th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 12th day I participated in the August more text, today brings you about the binary tree related algorithm problem is to convert the ordered array into binary search tree, the text is as follows:

The title

Given an array of integers, NUMs, whose elements have been sorted in ascending order, convert it to a highly balanced binary search tree.

A height-balanced binary tree is a binary tree where the absolute value of the height difference between the left and right subtrees of each node is not 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

Example 2:

Input: nums = [1,3] output: [3,1] explanation: both [1,3] and [3,1] are highly balanced binary search trees.Copy the code

Their thinking

A highly balanced binary search tree should be constructed.

First, the given arrays is ascending, and the characteristics of the binary search tree is also ascending sequence traversal of, so we can use any ascending in the array element as the root node, sequence of elements on the left side of the building left subtree, sequence of elements to the right of the building right subtree, thus obtained a binary search tree, but because it is demand highly balanced, So we need to select the middle element of the ascending sequence as the root node.

Determine the recursive function:

  1. Determine recursive parameters and return values: the parameters are an ascending array, the left range of the array, and the right range of the array; The return value is the built intermediate node
  2. Determine the terminating condition of recursion: when the interval left > right, it is the empty node and the recursion terminates;
  3. Determine the logic of single-layer recursion: first, take out the position of the middle element of the array, and then build the node with the element, and then divide the interval, and build the left subtree and right subtree of the node;

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        // The middle value of the array is the root node
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid-1);
        node.right = helper(nums, mid + 1, right);
        returnnode; }}Copy the code

The last

Complexity analysis

  • Time complexity: O(n), where n is the length of the array. Each number is accessed only once.

  • Space complexity: O(logn), where n is the length of the array. The spatial complexity does not take into account the return value, so the spatial complexity depends primarily on the depth of the recursion stack, which is O(logn).