When I first looked at this question, I found that the pass rate was 36%, which was quite amazing. Supposedly, it should be a relatively simple question. As a result, I didn’t do tree-related questions for a long time and even forgot how to do the basic questions. Fortunately, after two false attempts, the normal solution was found.

Verify the binary search tree

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.

Example 1:

Input: root = [2,1,3] Output: true 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 4.

Tip:

The number of nodes in the tree ranges from [1, 104] -231 <= node. val <= 231-1

Their thinking

The code location is: github.com/shidawuhen/…

To solve this problem, you need to understand the definition and properties of binary search trees.

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key is less than or equal to x.key. If y is a node in the right subtree of x, then y.key≥x.key.

In the binary search tree:

  1. If the left subtree of any node is not empty, the value of all nodes in the left subtree is not greater than the value of its root.

  2. If the right subtree of any node is not empty, the value of all nodes in the right subtree is not less than the value of its root node.

  3. The left and right subtrees of any node are binary search trees respectively.

According to the characteristics of binary search tree, we can find that the value of the left node of the root node must be smaller than that of the root node, and the value of the right node must be larger than that of the root node. Therefore, if the tree is traversed in middle order, the value should be monotonically increasing.

At the beginning, I forgot what binary search tree is, and when I wrote the initial version of the scheme, I did not consider using the middle order traversal, and I got two answers wrong.

code

// Order traversal, determine whether increment
var bstVal []int

func isValidBST(root *TreeNode) bool {
	bstVal = make([]int.0)
	dspVal(root)
	//fmt.Println(bstVal)
	for i := 1; i < len(bstVal); i++ {
		if bstVal[i]-bstVal[i- 1] < =0 {
			return false}}return true
}

func dspVal(node *TreeNode) {
	if node == nil {
		return
	}
	dspVal(node.Left)
	bstVal = append(bstVal, node.Val)
	dspVal(node.Right)
}

Copy the code

This code has an optimization point that allows you to determine in advance whether the value to be added to the bstVal meets the specification and the size of its previous value. If not, you can end execution as soon as possible.

var bstVal []int
// Order traversal optimization, determine whether increment
func isValidBSTOpt(root *TreeNode) bool {
	bstVal = make([]int.0)
	return dspValOpt(root)
}

func dspValOpt(node *TreeNode) bool {
	if node == nil {
		return true
	}
	res := dspValOpt(node.Left)
	if res == false {
		return false
	}
	if len(bstVal) > 0 && node.Val <= bstVal[len(bstVal)- 1] {
		return false
	}
	bstVal = append(bstVal, node.Val)
	res = dspValOpt(node.Right)
	if res == false {
		return false
	}
	return true
}
Copy the code