代码随想录二刷 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)  如果当前节点的值小于要找的值，则向当前节点的右子树寻找 

}