binary_search_tree.md

二叉搜索树

定义

• 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
• 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

应用

validate-binary-search-tree

验证二叉搜索树

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisValidBST(root*TreeNode) bool {
returndfs(root).valid
}
typeResultTypestruct{
maxintminintvalidbool
}
funcdfs(root*TreeNode)(resultResultType){
ifroot==nil{
result.max=-1<<63result.min=1<<63-1result.valid=truereturn
}
left:=dfs(root.Left)
right:=dfs(root.Right)
// 1、满足左边最大值<root<右边最小值 && 左右两边validifroot.Val>left.max&&root.Val<right.min&&left.valid&&right.valid {
result.valid=true
}
// 2、更新当前节点的最大最小值result.max=Max(Max(left.max,right.max),root.Val)
result.min=Min(Min(left.min,right.min),root.Val)
return
}
funcMax(a,bint)int{
ifa>b{
returna
}
returnb
}
funcMin(a,bint)int{
ifa>b{
returnb
}
returna
}

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

funcinsertIntoBST(root*TreeNode, valint) *TreeNode {
ifroot==nil{
return&TreeNode{Val:val}
}
ifroot.Val<val{
root.Right=insertIntoBST(root.Right,val)
}else{
root.Left=insertIntoBST(root.Left,val)
}
returnroot
}

delete-node-in-a-bst

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcdeleteNode(root*TreeNode, keyint) *TreeNode {
// 删除节点分为三种情况：// 1、只有左节点 替换为右// 2、只有右节点 替换为左// 3、有左右子节点 左子节点连接到右边最左节点即可ifroot==nil{
returnroot
}
ifroot.Val<key{
root.Right=deleteNode(root.Right,key)
}elseifroot.Val>key{
root.Left=deleteNode(root.Left,key)
}elseifroot.Val==key{
ifroot.Left==nil{
returnroot.Right
}elseifroot.Right==nil{
returnroot.Left
}else{
cur:=root.Right// 一直向左找到最后一个左节点即可forcur.Left!=nil{
cur=cur.Left
}
cur.Left=root.Leftreturnroot.Right
}
}
returnroot
}

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

typeResultTypestruct{
heightintvalidbool
}
funcisBalanced(root*TreeNode) bool {
returndfs(root).valid
}
funcdfs(root*TreeNode)(resultResultType){
ifroot==nil{
result.valid=trueresult.height=0return
}
left:=dfs(root.Left)
right:=dfs(root.Right)
// 满足所有特点：二叉搜索树&&平衡ifleft.valid&&right.valid&&abs(left.height,right.height)<=1{
result.valid=true
}
result.height=Max(left.height,right.height)+1return
}
funcabs(a,bint)int{
ifa>b{
returna-b
}
returnb-a
}
funcMax(a,bint)int{
ifa>b{
returna
}
returnb
}

练习

• validate-binary-search-tree
• insert-into-a-binary-search-tree
• delete-node-in-a-bst
• balanced-binary-tree