[leetcode] 450 and 98 (deletion and verification of binary search tree)

Search and insert of binary search tree The second part is the deletion and verification of binary search tree

This paper introduces how to use the characteristics of binary search tree to realize 「 Delete 」 and 「 verification 」 operation .

450. Delete nodes in binary search tree

solution ： recursive
Different from the deletion of ordinary binary tree , The binary search tree should adjust the tree nodes after deleting the corresponding nodes , Restore binary search tree . There are three cases of deleting nodes ：

1. The left subtree is empty . The root node of the right subtree replaces the current node .
2. Left subtree is not empty , The right subtree is empty . The root node of the left subtree replaces the current node .
3. The left and right subtrees are not empty . Use the right subtree minimum node （ Leftmost son ） To replace , And delete the minimum node .

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
        	return None
      
        if root.val == key:
        	#  situation 1
            if not root.left:
                return root.right
            #  situation 2
            if not root.right:
                return root.left
            #  situation 3
            #  Find the smallest node of the right subtree 
            minNode = self.getMin(root.right)
			#  Delete the smallest node from the right subtree 
            root.right = self.deleteNode(root.right, minNode.val)
			#  Replace the current node , Complete the delete operation 
            root.val = minNode.val
        elif root.val > key:
        	#  Enter the left subtree to search 
            root.left = self.deleteNode(root.left, key)
        else:
        	#  Enter the right subtree to search 
            root.right = self.deleteNode(root.right, key)
        
        return root
    #  Find the minimum node of the right subtree 
    def getMin(self, node):
        while node.left:
            node = node.left
        return node

98. Verify binary search tree

solution ： In the sequence traversal
Binary search tree （BST） The middle order traversal of is an ordered result , This can be used to determine whether the current tree is a correct binary search tree . The specific performance is to maintain a variable to store the previous calendar value , Judge whether the current node value is greater than the traversal , If more than , Update variable information , Otherwise return to False, Indicates that the subtree of the current node is not a binary search tree .
In the root The node is a subtree of the root node , The determination process of whether it is a binary search tree is as follows （ Any node 「 What to do 」：

1. First determine whether the left subtree is a binary search tree .
2. Determine whether the right subtree is a binary search tree .
3. Judge whether the current element meets BST nature
4. If the above conditions are met , with root The subtree with borrowing as the root node is a binary search tree , return True.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        maxValue = float("-inf")
        def traversal(root):
            nonlocal maxValue
            if not root:
                return True
            #  Determine whether the left subtree is BST
            left = traversal(root.left)
            if root.val <= maxValue:
                return False
            maxValue = root.val
            #  Judge whether the right subtree is BST
            right = traversal(root.right)
            #  All for True, Indicates that root The subtree with borrowing as the root node is BST.
            return left and right
        
        return traversal(root)

summary

1、 If the current node will be down ⾯ Of ⼦ Nodes have an overall impact , You can add ⻓ parameter list , Passing information by means of parameters .
2、 stay ⼆ Fork tree recursion framework , Extended out ⼀ set BST The code framework ：

3. According to the code framework BST Add, delete, check and modify .