Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10, NULL,5] Explanation: [0,-10,5, NULL,-3, NULL,9] is also accepted:Copy the code

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
Copy the code

Note:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order.
Copy the code

parsing

A list of integers, nums, whose elements are sorted in ascending order. We are asked to convert the integers in NUMS into a highly balanced binary search tree and return its root node.

A highly balanced binary tree is a special binary tree in which the two subtrees of each node differ in depth by no more than 1.

And the idea is very simple, as I’ve mentioned many times before, you can just do it recursively, but you just have to design the structure of the problem. If nums[:MID] is used as the root node, then we recurse to the left subtree for nums[:MID] and to the right subtree for nums[:MID], then we recurse to the right subtree for nums[:MID]. A highly balanced binary tree can be obtained.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:return None
        MID = len(nums)//2
        root = TreeNode(nums[MID])
        root.left = self.sortedArrayToBST(nums[:MID])
        root.right = self.sortedArrayToBST(nums[MID+1:])
        return root



        	      
		
Copy the code

The results

Runtime: Given in the Python online submission for Convert Sorted Array to Binary Search Tree. Given in Python online submissions for converting Sorted Array to Binary Search Tree.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation