Leetcode binary search tree

q98 Verify binary search tree

Subject portal

Answer key

Use preorder to traverse , Use dfs To traverse , The binary sort tree should satisfy that all nodes of the left subtree are smaller than the root node , All nodes of the right subtree are larger than the root node . Therefore, a maximum value and a minimum value are maintained in the parameter list of recursive functions , In left recursion , Update the maximum value to the current node , Because there should be no number larger than this maximum in the left subtree ; At the same time, when right recursion , Update the minimum value to the current node , Because there should be no number smaller than this minimum in the right subtree .

func isValidBST(root *TreeNode) bool {
    
	return dfs(root, math.MinInt64, math.MaxInt64)
}

func dfs(root *TreeNode, min, max int) bool {
    
	if root == nil {
    
		return true
	}
	//  Determine whether it is within this range 
	if root.Val <= min || root.Val >= max {
    
		return false
	}
	//  The maximum value of update left recursion is the current node 
	//  The minimum value of update right recursion is the current node 
	return dfs(root.Left, min, root.Val) && dfs(root.Right, root.Val, max)
}

q450 Delete nodes in binary search tree

Subject portal

Answer key

Delete BST The nodes in the , There are three situations :

1 If key < root.Val, The node to be deleted is BST The left subtree , Then recursively delete the left subtree
2 If key > root.Val, The node to be deleted is BST The right subtree , Then recursively delete the right subtree
3 If key = root.Val, Note that the node to be deleted is this node , This category is divided into the following three cases :

• No right or left subtree , Just delete it
• There are right subtrees , Replace the current node with the subsequent node , Then recursively delete the subsequent node in the right subtree
• There's a Zuozi tree , Replace the current node with the forward node , Then recursively delete the forward node in the left subtree

The way to find the forward node , It is to recursively traverse its right node in the left subtree of the current node , Until the right node is empty , The current node is the forward node .
The way to find the successor node is to recursively traverse its left node in the right subtree of the current node , Until the left node is empty , The current node is the successor node .

func deleteNode(root *TreeNode, key int) *TreeNode {
    
	if root == nil {
    
		return nil
		//  Go to the left tree 
	} else if key < root.Val {
    
		root.Left = deleteNode(root.Left, key)
		//  Go to the right subtree 
	} else if key > root.Val {
    
		root.Right = deleteNode(root.Right, key)
		//  The value of the current node is key
	} else {
    
		//  No right or left subtree , Delete directly 
		if root.Left == nil && root.Right == nil {
    
			root = nil
			//  There are right subtrees , Change the successor node to the current position , Then delete the successor node 
		} else if root.Right != nil {
    
			//  Replace 
			root.Val = Successor(root).Val
			//  Delete subsequent nodes 
			root.Right = deleteNode(root.Right, root.Val)
			//  There's a Zuozi tree , Change the forward node to the current position , Then delete the forward node 
		} else {
    
			root.Val = Predecessor(root).Val
			root.Left = deleteNode(root.Left, root.Val)
		}
	}
	return root
}

// Predecessor  Looking for forward nodes 
func Predecessor(node *TreeNode) *TreeNode {
    
	pre := node.Left
	for pre.Right != nil {
    
		pre = pre.Right
	}
	return pre
}

// Successor  Looking for successor nodes 
func Successor(node *TreeNode) *TreeNode {
    
	post := node.Right
	for post.Left != nil {
    
		post = post.Left
	}
	return post
}

q701 Insert operation in binary search tree

Subject portal

Answer key

Compare with the current node when inserting , If it is smaller than the current node, continue to traverse and insert it into the left subtree , If it is larger than the current node, continue to traverse and insert it into the right subtree .

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    
	if root == nil {
    
		return &TreeNode{
    Val: val}
	}
	p := root
	for p != nil {
    
		if val < p.Val {
    
			if p.Left == nil {
    
				p.Left = &TreeNode{
    Val: val}
				break
			}
			p = p.Left
		} else {
    
			if p.Right == nil {
    
				p.Right = &TreeNode{
    Val: val}
				break
			}
			p = p.Right
		}
	}
	return root
}