[leetcode] 700 and 701 (search and insert of binary search tree)

Binary search tree

Binary search tree as a classic data structure , It has the characteristics of quick insertion and deletion of linked list , It also has the advantage of fast array search ; So it's widely used , For example, in the file system and database system, this data structure is generally used for efficient sorting and retrieval operations .
BST Basic operation of ： Judge BST Legitimacy 、 increase 、 Delete 、 check .
This paper introduces how to use the characteristics of binary search tree to realize 「 Search for 」 and 「 increase 」 operation .

700. Search in binary search tree

solution ： recursive
The search of ordinary binary tree needs to traverse all nodes to judge in turn . For binary search tree , You can take advantage of its small on the left and large on the right , Do something like ⼆ Sub search operation , Improve search ⼀ The efficiency of elements . At this time, for any node 「 What to do 」 Judge as follows ：

1. If the current element is less than the target value , Then enter the left subtree search
2. If the current element is greater than the target value , Then enter the right subtree search
3. If equal , The current node is returned

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return None
        if root.val == val:
            return root
        elif root.val > val:
            result = self.searchBST(root.left, val)
        else:
            result = self.searchBST(root.right, val)
        
        return result

701. Insert operation in binary search tree

solution ： recursive
Operations on data structures ⽆⾮ Traverse + visit , Traversal is 「 look for 」, The interview is 「 Change 」. Specific to this question , insert ⼊⼀ Number , Is to find the plug first ⼊ Location , Then enter ⾏ insert ⼊ operation .
On ⼀ A question , We summarized BST Traversal framework in , Namely 「 look for 」 The problem of . Direct framing , add 「 Change 」 The operation of .⼀ Dan involves 「 Change 」, The function is going to return TreeNode type , And call recursion ⽤ The return value of ⾏ receive .

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:

        if not root:
        	#  Find the insertion location , Make changes 
            return TreeNode(val)
        
        if root.val > val:
        	#  Receive return value 
            root.left = self.insertIntoBST(root.left, val)
        else:
        	#  Receive return value 
            root.right = self.insertIntoBST(root.right, val)
        
        return root

summary

1. Experience the similarities and differences between the search process of binary search tree and ordinary binary tree .
2. Experience the difference between insert and search .