current position：Home>leetcode 108. Convert Sorted Array to Binary Search Tree（python）
leetcode 108. Convert Sorted Array to Binary Search Tree（python）
2022-01-30 03:05:13 【Wang Daya】
Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .
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.
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
Input: nums = [1,3] Output: [3,1] Explanation: [1,3] and [3,1] are both a height-balanced BSTs. Copy code
1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums is sorted in a strictly increasing order. Copy code
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 .
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
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
author[Wang Daya],Please bring the original link to reprint, thank you.
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 self-study 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 second-hand 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 built-in function and add a print function yourself
Python implements JS encryption algorithm in thousands of music websites
- 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, process-oriented, object-oriented 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, black-and-white 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