二叉搜索树
- 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
- 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。
验证二叉搜索树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
return dfs(root).valid
}
type ResultType struct{
max int
min int
valid bool
}
func dfs(root *TreeNode)(result ResultType){
if root==nil{
result.max=-1<<63
result.min=1<<63-1
result.valid=true
return
}
left:=dfs(root.Left)
right:=dfs(root.Right)
// 1、满足左边最大值<root<右边最小值 && 左右两边valid
if root.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
}
func Max(a,b int)int{
if a>b{
return a
}
return b
}
func Min(a,b int)int{
if a>b{
return b
}
return a
}
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root==nil{
return &TreeNode{Val:val}
}
if root.Val<val{
root.Right=insertIntoBST(root.Right,val)
}else{
root.Left=insertIntoBST(root.Left,val)
}
return root
}
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
// 删除节点分为三种情况：
// 1、只有左节点 替换为右
// 2、只有右节点 替换为左
// 3、有左右子节点 左子节点连接到右边最左节点即可
if root ==nil{
return root
}
if root.Val<key{
root.Right=deleteNode(root.Right,key)
}else if root.Val>key{
root.Left=deleteNode(root.Left,key)
}else if root.Val==key{
if root.Left==nil{
return root.Right
}else if root.Right==nil{
return root.Left
}else{
cur:=root.Right
// 一直向左找到最后一个左节点即可
for cur.Left!=nil{
cur=cur.Left
}
cur.Left=root.Left
return root.Right
}
}
return root
}
给定一个二叉树，判断它是否是高度平衡的二叉树。
type ResultType struct{
height int
valid bool
}
func isBalanced(root *TreeNode) bool {
return dfs(root).valid
}
func dfs(root *TreeNode)(result ResultType){
if root==nil{
result.valid=true
result.height=0
return
}
left:=dfs(root.Left)
right:=dfs(root.Right)
// 满足所有特点：二叉搜索树&&平衡
if left.valid&&right.valid&&abs(left.height,right.height)<=1{
result.valid=true
}
result.height=Max(left.height,right.height)+1
return
}
func abs(a,b int)int{
if a>b{
return a-b
}
return b-a
}
func Max(a,b int)int{
if a>b{
return a
}
return b
}
最近更新 3yr ago