代码随想录二刷 530 二叉搜索树的最小绝对差 98. 验证二叉搜索树 700. 二叉搜索树中的搜索
530 二叉搜索树的最小绝对差
代码如下
func getMinimumDifference(root *TreeNode) int {
var pre *TreeNode
res := math.MaxInt
var traverse func(root * TreeNode)
traverse = func(root * TreeNode) {
if root == nil {
return
}
traverse(root.Left) 定义两个指针，一个pre指针，一个为当前节点的root指针，因为是二叉搜索树，所以用中序遍历是递增序列
if pre != nil && root.Val - pre.Val < res { 当前一个节点不为空，那么比较前一个节点和当前节点的值，如果比之前的最小差值小，那么就更新最小差值
res = root.Val - pre.Val
}
pre = root 此时将pre指针更新，root指针指向下一个节点
traverse(root.Right)
}
traverse(root)
return res
}
func min(a,b int) int {
if a < b {
return a
}else {
return b
}
}
98. 验证二叉搜索树
代码如下
func isValidBST(root *TreeNode) bool {
var pre *TreeNode
var traverse func(root *TreeNode) bool
traverse = func(root *TreeNode) bool {
if root == nil { 如果是空节点也是二叉搜索树
return true
}
leftres := traverse(root.Left) 遍历左子树，并收集左子树的结果
if pre != nil && root.Val <= pre.Val { 因为用中序遍历二叉搜索树是一个升序序列。如果前一个节点比当前节点大，说明不是二叉搜索树
return false
}
pre = root 更新pre指针，并且root指向下一个节点
rightres := traverse(root.Right)
return rightres && leftres 返回左子树和右子树的结果
}
return traverse(root)
}
700. 二叉搜索树中的搜索
代码如下
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val {
return root
}
if root.Val > val { 利用二叉搜索树的特点，如果当前节点值大于要找的值，则向当前节点的左子树寻找
return searchBST(root.Left,val)
}
return searchBST(root.Right,val) 如果当前节点的值小于要找的值，则向当前节点的右子树寻找
}