98. validate Binary Search Tree

题目

给定一个二叉树，判断该二叉树是否是一个有效的二叉搜索树。

一个有效的二叉搜索树，其左子树的所有值小于该节点，右子树的所有值大于该节点。并且左右子树均为二叉搜索树。

解析

所以对每一个节点来说，
首先递归判断左子树是否为二叉搜索树，和右子树是否为二叉搜索树。
接下来要判断自身是否为二叉搜索树，判断的依据是，左子树的最大值是否小于当前节点，右子树的最小值是否大于当前节点。
由于任何一个节点自身并不知道是父节点的左节点还是右节点，所以我们需要维护一个节点的两个值，即最小值和最大值，返回给父节点后，父节点自行取相应的值进行比对并更新。

伪代码

is, rmin, max = valid(node.left)
if !is || max >= node.val
    return false, 0,0
is , min , rmax = valid(node.right)
if !is || min <= node.val
    return false, 0,0
return true, rmin, rmax

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    is, _ ,_ := valid(root)
    return is
}

func valid(node *TreeNode) (bool, int, int) {
    var is bool
    var lmin,lmax,rmin,rmax int
    if node.Left != nil {
        is, lmin, lmax = valid(node.Left)
        if !is || lmax >= node.Val {
            return false, 0, 0
        }
    }else {
        lmin = node.Val
    }
    
    if node.Right != nil {
        is, rmin, rmax = valid(node.Right)
        if !is || rmin <= node.Val {
            return false, 0, 0
        }
    }else {
        rmax = node.Val
    }
    return true, lmin, rmax
}

image.png

这种方式就显得很笨拙，二叉搜索树的特点是，其中序遍历是单调递增的，所以我们只需要判断上一个访问的节点值是否小于当前节点即可。按照通用二叉树的中序遍历方法。

for{
  if node == nil && stack == nil
    break
  if node == nil
    node = stack.pop()
    if pre == node.left
       if visit.val > node.val
            return false
       visit = node
    if pre == node.right
        pre = node
        node = nil
        continue
    else
      pre = nil
      node = node.right
      continue
  stack.push(node)
  node =node.left
}

代码

func isValidBST(root *TreeNode) bool {
    node := root
    stack := make([]*TreeNode, 1024)
    i:=0
    var pre *TreeNode
    var visit *TreeNode
    for {
        if node == nil && i == 0 {
            break
        }
        if node == nil {
            node = stack[i-1]
            i--
            if pre == node.Left {
                if visit != nil && visit.Val >= node.Val {
                    return false
                }
                visit = node
            }
            if pre == node.Right {
                pre = node
                node = nil
                continue
            }else {
                i++
                pre = nil
                node = node.Right
                continue
            }
        }
        stack[i] = node
        i++
        node=node.Left
    }
    return true
}

image.png