判断是不是二叉搜索树

package main

import . "nc_tools"
import "math"
import "fmt"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if root.Val == 2147317028 {
	levelOrder(root.Left)
	}

	isValidLeft, _, leftMax := validBSTNode(root.Left)
	isValidRight, rightMin, _ := validBSTNode(root.Right)
	fmt.Println(isValidLeft)
	fmt.Println(isValidRight)
	fmt.Println(leftMax)
	fmt.Println(rightMin)
	if leftMax != math.MinInt64 && int64(root.Val) <= leftMax {
		return false
	}
	if rightMin != math.MaxInt64 && int64(root.Val) >= rightMin {
		return false
	}
	return isValidLeft && isValidRight
}

func validBSTNode(root *TreeNode) (bool, int64, int64) {
	if root == nil {
		return true, math.MaxInt64, math.MinInt64
	}
	min, max := int64(root.Val), int64(root.Val)
	isValidLeft, leftMin, leftMax := validBSTNode(root.Left)
	isValidRight, rightMin, rightMax := validBSTNode(root.Right)

	if leftMax > max {
		max = leftMax
	}
	if rightMax > max {
		max = rightMax
	}
	if leftMin < min {
		min = leftMin
	}
	if rightMin < min {
		min = rightMin
	}
	return isValidLeft && isValidRight, min, max
}

func v2(root *TreeNode) bool {
	// arr 用来装当前层的所有node
	arr := []*TreeNode{root}
	res := make([][]*TreeNode, 0)
	for len(arr) > 0 {
		// 记录当前层次要遍历的总长度
		currentLevelLen := len(arr)
		// 记录当前层次遍历的结果
		curLevel := make([]*TreeNode, 0, len(arr))
		for i := 0; i < currentLevelLen; i++ {
			curLevel = append(curLevel, arr[i])
			if arr[i] == nil {
				continue
			}
			arr = append(arr, arr[i].Left)
			arr = append(arr, arr[i].Right)
		}
		// arr 是复用变量，使用结束后只留下下一层的元素
		arr = arr[currentLevelLen:]
		res = append(res, curLevel)
	}

	for index, lArr := range res {
		fmt.Printf("第%v行：", index+1)
		for _, lNum := range lArr {
			if lNum == nil {
				fmt.Print("# ")
			} else {
				fmt.Print(fmt.Sprint(lNum.Val) + " ")
			}
		}
		fmt.Println()
	}

	return false
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	// arr 用来装当前层的所有node
	arr := []*TreeNode{root}
	res := make([][]int, 0)
	for len(arr) > 0 {
		// 记录当前层次要遍历的总长度
		currentLevelLen := len(arr)
		// 记录当前层次遍历的结果
		curLevel := make([]int, 0, len(arr))
		for i := 0; i < currentLevelLen; i++ {
			if arr[i] == nil {
				continue
			}
			curLevel = append(curLevel, arr[i].Val)
			if arr[i].Left != nil {
				arr = append(arr, arr[i].Left)
			}
			if arr[i].Right != nil {
				arr = append(arr, arr[i].Right)
			}
		}
		// arr 是复用变量，使用结束后只留下下一层的元素
		arr = arr[currentLevelLen:]
		res = append(res, curLevel)
	}
	max := res[1][0]
	for index, lArr := range res {
		if index == 0 {
			continue
		}
		for _, lNum := range lArr {
			if lNum > max {
				max = lNum
			}
		}
	}
	fmt.Printf("max:%v\n", max)
	return res
}

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
    ok, _, _ := isBST(root)
	return ok
}

func isBST(root *TreeNode) (bool, int, int) {
    if root == nil {
        return true, -1 << 31, 1 << 31 -1
    }
	if root != nil && root.Left == nil && root.Right == nil  {
		return true, root.Val, root.Val
	}
    isl, maxl, minl := isBST(root.Left)
    isr, maxr, minr := isBST(root.Right)
    if maxr == 1 << 31 -1 {
        maxr = root.Val
    }
    if minl == -1 << 31 {
        minl = root.Val
    }
    if isl && isr && root.Val >= maxl && root.Val <= minr {
        return true, maxr, minl
    } else {
        return false, maxr, minl
    }
}

func isValidBST(root *TreeNode) bool {
	var dfs func(root *TreeNode)
	var result bool = true
	var pre *TreeNode
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if pre == nil {
			pre = root
		} else {
			if pre.Val > root.Val {
				result = false
				pre = root
				return
			}
			pre = root
		}
		dfs(root.Right)
	}
	dfs(root)
	return result
	// write code here
}