Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Original title: #### 98. Validate binary search trees

Given a binary tree, 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.

Answer:

To verify the effectiveness of binary search tree, we can start from its definition and characteristics.

Starting from the root of an effective binary search tree, the values of all nodes of the left subtree are smaller than it, and the values of all nodes of the right subtree are larger than it. According to the values of the two nodes, the legal value ranges of all nodes of the left and right subtrees can be determined respectively. And because its left and right subtrees meet the above requirements, that is, they are effective binary search trees, so it can carry out recursive verification. Take any node as the starting point, determine the value range of its left and right nodes according to its value range (and nodes can take any value) and its own value. If the value of the left and right nodes is within the value range, and the left and right subtrees are valid binary search trees, then the verification can be passed.

In addition, the derivation condition of a recursive call is that a null pointer is traversed, so it should be treated as a valid node that has been validated.

Final code:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
private boolean dfs(TreeNode node, long minValue, long maxValue) {
    return node == null|| (node.val > minValue && node.val < maxValue && dfs(node.left, minValue, node.val) && dfs(node.right, node.val, maxValue)); }}Copy the code

In addition to this method, there is a simple method. The middle-order traversal result of binary search tree is an ascending sequence, so we can carry out middle-order traversal of binary tree, as long as the value of each node traversed is greater than the value of the last node traversed, then the binary tree is valid search binary tree.