current position：Home>leetcode 108. Convert Sorted Array to Binary Search Tree（python）
leetcode 108. Convert Sorted Array to Binary Search Tree（python）
20220130 03:05:13 【Wang Daya】
Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .
describe
Given an integer array nums where the elements are sorted in ascending order, convert it to a heightbalanced binary search tree.
A heightbalanced 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 code
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a heightbalanced BSTs.
Copy code
Note:
1 <= nums.length <= 10^4
10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order.
Copy code
analysis
According to the meaning , Is to give a list of integers nums , The elements are lists that have been sorted in ascending order . The title requires us to nums The integer in is transformed into a highly balanced binary search tree , Returns its root node .
Highly balanced binary tree is a special kind of binary tree , The depth difference between the two subtrees of each node is no more than 1.
The idea is simple , Mentioned many times before , Just use recursion to solve it directly , Just design the structure according to the meaning of the topic . Here is the sorted list nums Into a highly balanced binary tree , The key is to find the root node first , So just put nums[MID] As the root node , Then on nums[:MID] Recursion of the left subtree , Yes nums[MID+1:] Recursion of right subtree , Then we can get a highly balanced binary tree that conforms to the meaning of the question .
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 code
Running results
Runtime: 97 ms, faster than 32.83% of Python online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 16 MB, less than 92.78% of Python online submissions for Convert Sorted Array to Binary Search Tree.
Copy code
Original link ：leetcode.com/problems/co…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201300305120824.html
The sidebar is recommended
 Getting started with Python  object oriented  special methods
 Using linear systems in python with scipy.linalg
 Fast power modulus Python implementation of large numbers
 Python architects recommend the book "Python programmer's Guide" which must be read by selfstudy Python architects. You are welcome to take it away
 Decoding the verification code of Taobao slider with Python + selenium, the road of information security
 Python game development, pyGame module, python implementation of skiing games
 Python collects and monitors system data  psutil
 Python + selenium automated test: page object mode
 You can easily get started with Excel. Python data analysis package pandas (IV): any grouping score bar
 Python ThreadPoolExecutor restrictions_ work_ Queue size
guess what you like

Python generates and deploys verification codes with one click (Django)

[Python kaggle] pandas basic exercises in machine learning series (6)

Using linear systems in python with scipy.linalg

Using Python to realize national secondhand housing data capture + map display

How to make Python run faster? Six tips!

Python chat room (Tkinter writing interface, streaming, socket to realize private chat, group chat, check chat records, Mysql to store data)

This pandas exercise must be successfully won

[algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)

Understand Python's builtin function and add a print function yourself

Python implements JS encryption algorithm in thousands of music websites
Random recommended
 leetcode 35. Search Insert Position（python）
 [introduction to Python visualization]: 12 small examples of complete data visualization, taking you to play with visualization ~
 Learning this Python library can reduce at least 100 lines of code
 leetcode 67. Add Binary（python）
 Regular re parameter replacement of Python 3 interface automation test framework
 V. pandas based on Python
 Only 15 lines of code is needed for face detection! (using Python and openCV)
 [Python crawler Sao operation] you can crawl Sirius cinema movies without paying
 leetcode 69. Sqrt(x)（python）
 Teach you to read the source code of Cpython (I)
 Snowball learning started in the fourth quarter of Python. One needs three meals. I have a new understanding of Python functional programming, processoriented, objectoriented and functional
 leetcode 88. Merge Sorted Array（python）
 Don't you know more about a python library before the end of 2021?
 Python crawler web page parsing artifact XPath quick start teaching!!!
 Use Python and OpenCV to watermark the image
 String and related methods of Python data type introduction
 Heapq module of Python module
 Introduction to beautiful soup of Python crawler weapon, detailed explanation, actual combat summary!!!
 Event loop of Python collaboration series
 Django docking pin login system
 [recalling the 1970s] using Python to repair the wonderful memories of parents' generation, blackandwhite photos become color photos
 You used to know Python advanced
 Pyinstaller package Python project
 2021 IEEE programming language rankings: Python tops the list!
 Implementation of Python automatic test control
 Python advanced: [Baidu translation reverse] graphic and video teaching!!!
 Do you know the fuzzy semantics in Python syntax?
 [Python from introduction to mastery] (XXVII) learn more about pilot!
 Playing excel office automation with Python
 Some applications of heapq module of Python module
 Python and go languages are so popular, which is more suitable for you?
 Python practical skills task segmentation
 Python simulated Login, numpy module, python simulated epidemic spread
 Python opencv contour discovery function based on image edge extraction
 Application of Hoff circle detection in Python opencv
 Python reptile test ox knife (I)
 Day 1: learn the Django framework of Python development
 django  minio_ S3 file storage service
 [algorithm learning] 02.03 Delete intermediate nodes (Java / C / C + + / Python / go)
 Learning in Python + opencv  extracting corners