package main

import (
	"fmt"
	"math"
)

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

// 验证一个二叉树是否为BST ，尝试使用指针法(不好使，在递归中，每个栈的代码都是一样的，如果要分辨左右分支，需要很多的if，没有必要，还是多传几个参数把 )
// 关键：传入lower 和 upper需要在当前节点位置决定
func isValidBST(root *TreeNode) bool {
	return helper(root, math.MinInt64 , math.MaxInt64)
}

func helper(node *TreeNode, lower ,upper int) bool {
	if node == nil {
		return true
	}
	if node.Val >= upper || node.Val <= lower{
		return false
	}
	return helper(node.Left , lower , node.Val) && helper(node.Right , node.Val , upper)
}

func main() {
	n1 , n2 , n3, n4 ,n5 := &TreeNode{5,nil,nil},&TreeNode{1,nil,nil},&TreeNode{4,nil,nil},&TreeNode{3,nil,nil},&TreeNode{6,nil,nil}
	n1.Left = n2
	n1.Right = n3
	n3.Left = n4
	n3.Right = n5
	fmt.Println(isValidBST(n1))
}