Go:Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var pre *TreeNode
func isValidBST(root *TreeNode) bool {
sign := true
pre = nil
convertToBST(root, &sign)
return sign
}
func convertToBST(root *TreeNode, sign *bool) {
if root != nil && *sign == true {
convertToBST(root.Left, sign)
if pre != nil && pre.Val >= root.Val {
*sign = false
}
pre = root
convertToBST(root.Right, sign)
}
}
发表评论
要发表评论,您必须先登录。