二叉搜索树

定义

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

应用

验证二叉搜索树
1
/**
2
* Definition for a binary tree node.
3
* type TreeNode struct {
4
* Val int
5
* Left *TreeNode
6
* Right *TreeNode
7
* }
8
*/
9
func isValidBST(root *TreeNode) bool {
10
return dfs(root).valid
11
}
12
type ResultType struct{
13
max int
14
min int
15
valid bool
16
}
17
func dfs(root *TreeNode)(result ResultType){
18
if root==nil{
19
result.max=-1<<63
20
result.min=1<<63-1
21
result.valid=true
22
return
23
}
24
25
left:=dfs(root.Left)
26
right:=dfs(root.Right)
27
28
// 1、满足左边最大值<root<右边最小值 && 左右两边valid
29
if root.Val>left.max && root.Val<right.min && left.valid && right.valid {
30
result.valid=true
31
}
32
// 2、更新当前节点的最大最小值
33
result.max=Max(Max(left.max,right.max),root.Val)
34
result.min=Min(Min(left.min,right.min),root.Val)
35
return
36
}
37
func Max(a,b int)int{
38
if a>b{
39
return a
40
}
41
return b
42
}
43
func Min(a,b int)int{
44
if a>b{
45
return b
46
}
47
return a
48
}
Copied!
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
1
func insertIntoBST(root *TreeNode, val int) *TreeNode {
2
if root==nil{
3
return &TreeNode{Val:val}
4
}
5
if root.Val<val{
6
root.Right=insertIntoBST(root.Right,val)
7
}else{
8
root.Left=insertIntoBST(root.Left,val)
9
}
10
return root
11
}
Copied!
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
1
/**
2
* Definition for a binary tree node.
3
* type TreeNode struct {
4
* Val int
5
* Left *TreeNode
6
* Right *TreeNode
7
* }
8
*/
9
func deleteNode(root *TreeNode, key int) *TreeNode {
10
// 删除节点分为三种情况:
11
// 1、只有左节点 替换为右
12
// 2、只有右节点 替换为左
13
// 3、有左右子节点 左子节点连接到右边最左节点即可
14
if root ==nil{
15
return root
16
}
17
if root.Val<key{
18
root.Right=deleteNode(root.Right,key)
19
}else if root.Val>key{
20
root.Left=deleteNode(root.Left,key)
21
}else if root.Val==key{
22
if root.Left==nil{
23
return root.Right
24
}else if root.Right==nil{
25
return root.Left
26
}else{
27
cur:=root.Right
28
// 一直向左找到最后一个左节点即可
29
for cur.Left!=nil{
30
cur=cur.Left
31
}
32
cur.Left=root.Left
33
return root.Right
34
}
35
}
36
return root
37
}
Copied!
给定一个二叉树,判断它是否是高度平衡的二叉树。
1
type ResultType struct{
2
height int
3
valid bool
4
}
5
func isBalanced(root *TreeNode) bool {
6
return dfs(root).valid
7
}
8
func dfs(root *TreeNode)(result ResultType){
9
if root==nil{
10
result.valid=true
11
result.height=0
12
return
13
}
14
left:=dfs(root.Left)
15
right:=dfs(root.Right)
16
// 满足所有特点:二叉搜索树&&平衡
17
if left.valid&&right.valid&&abs(left.height,right.height)<=1{
18
result.valid=true
19
}
20
result.height=Max(left.height,right.height)+1
21
return
22
}
23
func abs(a,b int)int{
24
if a>b{
25
return a-b
26
}
27
return b-a
28
}
29
func Max(a,b int)int{
30
if a>b{
31
return a
32
}
33
return b
34
}
Copied!

练习

最近更新 1yr ago
复制链接