“This is the 23rd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Determines whether a tree is a binary search tree

Verify binary search trees

Topic describes

You are given the root node of a binary tree to determine whether it is a valid binary search tree.

The effective binary search tree is defined as follows:

  • 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

The sample

Example 1

Input: root = [2,1,3] output: trueCopy the code

Example 2

Input: root = [5,1,4,null,null,3,6] output: false description: the root node is 5, but the right child node is 4Copy the code

Tip:

  • The number of nodes in the tree ranges from[1, 10 ^ 4) 内
  • 2^31 <= Node.val <= 2^31 - 1

The problem solving

Solution one: recursion

Train of thought

If the left and right subtrees of a node are binary search trees, then it is itself a binary search tree. According to the instructions given in the question, a binary search tree satisfies the following conditions:

  • 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

One mistake is that it is easy to write code that only determines whether the root node and its left and right subtrees are balanced binary trees. This is not true, for example, it is not true to write:

func isValidBST(root *TreeNode) bool { if root == nil { return true } return isValid(root) } func isValid(root *TreeNode) bool { if root == nil { return true } if root.Left == nil && root.Right == nil { return true } if root.Left ! = nil && root.Left.Val >= root.Val { return false } if root.Right ! = nil && root.Right.Val <= root.Val { return false } return isValid(root.Left) && isValid(root.Right) }Copy the code

In this case, the code above will fail

The code only recognizes that 5, 4, 6, and 6, 3, 7 are binary search trees, but the whole tree is not a binary search tree

So we need to think differently. It is easy to think of recursion. Assuming that root is the subtree with the root, all nodes in the subtree should be judged to be in the interval (open interval) of (min, Max). If the value of root is not in the interval of (min, Max), it indicates that the condition of binary search tree is not met and can be returned directly. Otherwise, continue traversing the left and right subtrees

When recursing the left subtree, the Max of the upper boundary should be replaced by root.Val (the value of the current node). Similarly, when recursing to the right subtree, min at the bottom should be replaced by root.val

code

func isValidBST(root *TreeNode) bool { return isValid(root, math.MinInt64, math.MaxInt64) } func isValid(root *TreeNode, min, max int) bool { if root == nil { return true } if root.Val <= min || root.Val >= max { return false } // //isValid(root.right, root.val, Max), Return isValid(root.left, min, root.val) &&isValid (root.right, root.val, Max)}Copy the code

Solution two: order traversal

Train of thought

Because we know that for a two-interpolation search tree, its middle-order traversal can print the values of all nodes in ascending order. This feature is used to solve the problem, because in the process of traversal, it is necessary to compare whether the value of the current node is greater than the value of the previous node, so it is difficult to add this layer of judgment in recursive traversal, so it is necessary to use the non-recursive traversal of the middle order

In my previous post, I shared in detail the recursive and non-recursive traversal of the front, middle, and back order of trees, as well as the order traversal, if you are not familiar with it, you can go here. The binary tree variables are the basis of all the tree problems, and you’ll see that all the tree problems are variations of traversing the tree, but they add some operations to the traversing process

The middle-order non-recursive traversal of binary tree needs the help of stack, so the stack is used to achieve it, the specific code is as follows

code

Func isValidBST2(root *TreeNode) bool {nodeStack := []*TreeNode{} preNodeVal := math.minint64 for len(nodeStack) ! = 0 || root ! = nil { for root ! = nil { nodeStack = append(nodeStack, root) root = root.Left } root = nodeStack[len(nodeStack)-1] nodeStack = nodeStack[:len(nodeStack)-1] if root.Val <= preNodeVal { return false } preNodeVal = root.Val root = root.Right } return true }Copy the code