【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

  • Construct binary tree | Go theme month by traversing sequence from middle order to back order

  • Recent common ancestor of binary tree | Go theme month

  • Binary tree serialization and deserialization | Go topic month

Leecode 98. Validate binary search trees

Given a binary tree, determine whether it is a valid binary search tree.

Suppose a binary search tree has the following characteristics:

The left subtree of a node contains only numbers less than the current node.

The right subtree of a node only contains numbers greater than the current node.

All left and right subtrees must themselves also be binary search trees.

Example 1:

Example 2:

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}

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





Copy the code

We know that the sequence of values obtained by “middle-order traversal” of binary search tree must be in ascending order, which enlights us to check whether the value of the current node is greater than the value of the previous middle-order traversal node in real time during middle-order traversal. If both are greater than, the sequence is ascending and the whole tree is a binary search tree, otherwise it is not. In the following code, we use the stack to simulate the process of sequential traversal.

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64
    for len(stack) > 0|| root ! =nil {
        forroot ! =nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)- 1]
        stack = stack[:len(stack)- 1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }
    return true
}

Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️