Topic link

The title has described the characteristics of binary search tree, as long as according to the characteristics to verify. There are two ways of thinking about it

  • To verify that the value of the current node is greater than the value of the previous node in the traversal process
  • Verify that the current subtree is bounded between a minimum and a maximum value

The following is the specific solution. The following code has been submitted and approved.

Method a

Order traversal, recursive implementation.

func isValidBST(root *TreeNode) bool {
    var prev *TreeNode
    var isValid func(*TreeNode) bool
    Call isValid recursively
    isValid = func(root *TreeNode) bool {
        // Termination conditions
        if root == nil {
            return true
        }
        if! isValid(root.Left) {return false
        }
        // Process the current child root node
        ifprev ! =nil {
            // Compare with the value of the previous node
            if prev.Val >= root.Val {
                return false
            }
        }
        prev = root
        return isValid(root.Right)
    }
    return isValid(root)
}
Copy the code

Method 2

Middle order traversal, iterative method.

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    var (
        sk Stack
        prev *TreeNode
        curr = root
    )
    for {
        ifcurr ! =nil {
            sk.Push(curr)
            curr = curr.Left
        } else if! sk.IsEmpty() { node := sk.Peek() sk.Pop()// Compare the current node with the previous node
            ifprev ! =nil {
                if prev.Val >= node.Val {
                    return false
                }
            }
            prev = node
            curr = node.Right
        } else {
            break}}return true
}

/ / stack
type Stack struct {
    data []*TreeNode
}

func (o *Stack) Len(a) int {
    return len(o.data)
}

func (o *Stack) IsEmpty(a) bool {
    return len(o.data) == 0
}

func (o *Stack) Push(node *TreeNode) {
    o.data = append(o.data, node)
}

func (o *Stack) Peek(a) *TreeNode {
    if o.IsEmpty() {
        panic("Stack is empty")}return o.data[len(o.data)- 1]}func (o *Stack) Pop(a) {
    if o.IsEmpty() {
        panic("Stack is empty")
    }
    o.data = o.data[:len(o.data)- 1]}Copy the code

Method three

Order traversal, recursion. The idea is the characteristic of binary search tree, the value of all nodes in the left subtree is less than the value of its root node, and the value of all nodes in the right subtree is greater than the value of its root node.

func isValidBST(root *TreeNode) bool {
    return isValid(root, nil.nil)}Call isValid recursively
func isValid(root, min, max *TreeNode) bool {
    // Recursive termination condition
    if root == nil {
        return true
    }
    // Verify that the current node is greater than the minimum
    ifmin ! =nil {
        if root.Val <= min.Val {
            return false}}// Verify that the current node is less than the maximum
    ifmax ! =nil {
        if root.Val >= max.Val {
            return false}}// The value of all nodes in the left subtree is less than the value of its root node.
    // The value of all nodes in the right subtree is greater than the value of its root node.
    if! isValid(root.Left, min, root) || ! isValid(root.Right, root, max) {return false
    }
    return true
}
Copy the code

Method four

Middle order traversal, recursion. The idea is the same as solution three.

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func isValidBST(root *TreeNode) bool {
    return isValid(root, nil.nil)}func isValid(root, min, max *TreeNode) bool {
    if root == nil {
        return true
    }
    if! isValid(root.Left, min, root) {return false
    }
    ifmin ! =nil {
        if root.Val <= min.Val {
            return false}}ifmax ! =nil {
        if root.Val >= max.Val {
            return false}}return isValid(root.Right, root, max)
}
Copy the code

Solution to five

Backward traversal, recursion. The idea is the same as solution three.

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func isValidBST(root *TreeNode) bool {
    return isValid(root, nil.nil)}func isValid(root, min, max *TreeNode) bool {
    if root == nil {
        return true
    }
    if! isValid(root.Left, min, root) || ! isValid(root.Right, root, max) {return false
    }
    ifmin ! =nil {
        if root.Val <= min.Val {
            return false}}ifmax ! =nil {
        if root.Val >= max.Val {
            return false}}return true
}
Copy the code