This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

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] Explanation: Another accepted tree isCopy the code

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25 Output: [25] 40,20,60,10,30,50,70, null, null,Copy the code

Example 3:

Input: root = [4,2,7,1,3, null, null, null, null, null, null], val = 5 Output:,2,7,1,3,5 [4]Copy the 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 the code

parsing

Insert val into the binary tree and return the root node. Val is guaranteed to be a value that does not exist in root, and there may be multiple binary trees. You just need to return any one of them.

It’s the old way of doing it recursively, but you just need to know the basic properties of a binary tree, which is that the left subtree is smaller than the root, and the right subtree is larger than the root. Then use recursion:

  • If the root node root is empty, initialize a node with val and return
  • If the value of root is less than val, val should be in the right subtree of root, so recursive node insertion is performed on the right subtree of root
  • If the value of root is greater than val, val should be in the left subtree of root, so recursive node insertion is performed on the left subtree of root
  • Finally, the current root node root is returned

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 the code

The results

Given the linked list in the Python online submission into a Binary Search Tree. Memory Usage: 10000 ms The linked submissions in the Python online list for Insert into a Binary Search TreeCopy the code

parsing

In fact, with more awkward ideas, can be divided into several steps:

  • Initialize an L empty list to hold all node values
  • Define getListFromBST to recursively traverse the values of all nodes, all stored in L
  • Let’s add val to L and sort L
  • SortedListToBST uses recursion to build a Binary Tree from an ascending list. Leetcode 108. Convert Sorted Array to Binary Search Tree

Obviously this method is a lot of tedious, not as simple and clear 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 the code

The results

Given in the Python online submission into a Binary Search Tree. Memory Usage: Each node in the Python online submissions list for Insert into a Binary Search Tree.Copy the code

Original link: leetcode.com/problems/in…

Your support is my biggest motivation