current position：Home>leetcode 701. Insert into a Binary Search Tree （python）
leetcode 701. Insert into a Binary Search Tree （python）
20220130 03:13:34 【Wang Daya】
This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund
describe
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
Copy code
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Copy code
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
Copy code
Note:
The number of nodes in the tree will be in the range [0, 10^4].
10^8 <= Node.val <= 10^8
All the values Node.val are unique.
10^8 <= val <= 10^8
It's guaranteed that val does not exist in the original BST.
Copy code
analysis
According to the meaning , Is to give the root node of a binary tree root , Then give a value val , The title requires us to val The node of value is inserted into the binary tree , And return to the root node , The title guarantees val It doesn't exist in root Value , And there may be many kinds of binary trees , Just return any one of them .
Or the old way to use recursion to solve problems , Here we only need to know the basic properties of binary tree , That is, the value of the left subtree is smaller than that of the root node , The value of the right subtree is larger than that of the root node . Then use recursion ：
 If the root node root It's empty , Then use val Initialize a node and return
 If the root node root The value is less than val , explain val belong root The right subtree , So recursion is right root Recursive node insertion for the right subtree of
 If the root node root The value is greater than val , explain val belong root The left subtree , So recursion is right root Recursive node insertion in the left subtree of
 Finally, return the current root node root
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 insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
node = TreeNode(val)
return node
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
else:
root.left = self.insertIntoBST(root.left, val)
return root
Copy code
Running results
Runtime: 166 ms, faster than 23.65% of Python online submissions for Insert into a Binary Search Tree.
Memory Usage: 17.6 MB, less than 41.28% of Python online submissions for Insert into a Binary Search Tree.
Copy code
analysis
In fact, I use a clumsy idea , You can do it in several steps ：
 Initialize a L The empty list is used to store all node values
 Definition getListFromBST The function uses recursion to traverse the values of all nodes , Save all L in
 take val Also joined L And then to L Sort
 Defined function sortedListToBST Use recursion to build a binary tree for the list that has been ascending , This operation is the same as this problem leetcode 108. Convert Sorted Array to Binary Search Tree（python）
Obviously, this method is a lot cumbersome , It's not as concise as the previous method .
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 __init__(self):
self.L = []
def getListFromBST(self, root):
if not root:return
self.getListFromBST(root.left)
self.L.append(root.val)
self.getListFromBST(root.right)
def sortedListToBST(self, nums):
if not nums: return
MID = len(nums) // 2
root = TreeNode(nums[MID])
root.left = self.sortedListToBST(nums[:MID])
root.right = self.sortedListToBST(nums[MID+1:])
return root
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
self.getListFromBST(root)
self.L.append(val)
self.L.sort()
return self.sortedListToBST(self.L)
Copy code
Running results
Runtime: 389 ms, faster than 5.01% of Python online submissions for Insert into a Binary Search Tree.
Memory Usage: 19.4 MB, less than 16.83% of Python online submissions for Insert into a Binary Search Tree.
Copy code
Original link ：leetcode.com/problems/in…
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/202201300313324606.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