The title information

Subject address: leetcode-cn.com/problems/va…

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:

Input:2
   / \
  1   3Output:true
Copy the code

Example 2:

Input:5
   / \
  1   4
     / \
    3   6Output:falseThe input is: [5.1.4.null.null.3.6]. The value of the root is5, but its right child value is4 。
Copy the code

Solution one: recursion

And just like in the last problem, it’s a good idea to think about recursion, getting smaller and smaller on the left, getting bigger and bigger on the right. This place is prone to an illusion. Error thinking and code:The left node recurses but it does not end with any children and returns true. The right node recurses as well. The right node recurses because it does not end with any children and the left node does the same. The entire recursive completion is ultimately true, but since 3 is smaller than root 5 it should not satisfy the binary search tree in the left subtree

public boolean isValidBST(TreeNode root) {
    if(root == null) return true;
    if(root.left ! =null && root.left.val >= root.val)
        return false;
    if(root.right ! =null && root.right.val <= root.val)
        return false;
    return isValidBST(root.left) && isValidBST(root.right);
}
Copy the code

So the question is what are we comparing?For leaf 2 it has no limit if it’s less than 3, for leaf 6 it has to be greater than 3 and less than 5 which means that if we go to the left it’s small and then there’s an upper limit that we can’t go beyond, and if we go to the right it’s big and then there’s a lower limit.In accordance with the whole process as shown in the figure above, starting from the root node, we enter recursion to the left. After we move to the left, all the values on this side are less than the upper limit 5 and 3 is less than 5. We continue recursion and find 2, the upper limit of the tree after 2 is 3

The code is as follows:

public boolean isValidBST(TreeNode root) {
    return process(root, null.null);
}
// Recursive method
public boolean process(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    if(min ! =null && node.val <= min) return false;
    if(max ! =null && node.val >= max) return false;
    if(! process(node.right, node.val, max))return false;
    if(! process(node.left, min, node.val))return false;
    return true;
}
Copy the code

Solution two: order traversal

Middle order traversal is a tree traversal method, first count the left subtree in the middle of the number and then count the right subtree, so through middle order traversal if it is true, the binary search tree is a small sequenceOrder traversal in the figure above: [2,3,6,5,3,6,7]

// record the previous one
Integer pre = null;
public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    // Access the left subtree
    if(! isValidBST(root.left))return false;
    // Access current node: if the current node is less than or equal to the previous node in the middle traversal. That does not meet the
    if(pre ! =null && root.val <= pre) return false;
    pre = root.val;
    // Access the right subtree
    return isValidBST(root.right);
}
Copy the code

conclusion

In fact, both solutions are depth-first. Use different traversal procedures and then you need to figure out how to handle the logic of judgment in this traversal.