Topic describes

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 3 Output:true
Copy the code

Example 2:

Input: 5 / \ 1 4 / \ 3 6 output:falseInput: [5,1,4,null,null,3,6] The root node has a value of 5, but its right child node has a value of 4.Copy the code

Title link:

Leetcode-cn.com/problems/va…

Wrong ideas

Well, when I watched professor Qin Chao’s algorithm video before, he always stressed that we should observe binary search trees from the latitude of subtrees, rather than child nodes, and silently nodded at that time. Result this problem, come up is a shuttle, still planted on this mistake.

Isn’t it simple at first glance? Each time the current node is compared to the left and right child nodes, the recursion continues until the entire tree is traversed, and the recursion terminates when it encounters an illegal condition halfway through.

The code is as follows:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
            if(root.left ! =null) {
                if (root.left.val > root.val) return false;
                isValidBST(root.left);
            }

            if(root.right ! =null) {
                if (root.right.val < root.val) return false;
                isValidBST(root.right);
            }

        return true; }}Copy the code

In a case like the following, which is clearly a non-compliant binary search tree, the program only determines whether node 9 is smaller than node 11, but ignores the minimum lower bound 10.

Set upper and lower boundaries

Learning from the previous lessons, we know that when traversing the binary tree, we need to inform the upper and lower boundaries. For example, in the above example, when traversing the node 9, we should tell it the upper boundary = 11 and the lower boundary = 10 (the upper boundary of the parent node). Detection finds that 9 < lower, So we know that this is a non-compliant binary search tree.

The code is as follows:

    public boolean isValidBST(TreeNode root) {
        return helper(root, null.null);
    }

    public boolean helper(TreeNode root, Integer lower, Integer upper) {
        if (root == null) return true;

        if(lower ! =null && root.val <= lower) return false;
        if(upper ! =null && root.val >= upper) return false;
				
        // Update the upper bound as you traverse the left node
        if(! helper(root.left, lower, root.val))return false;
        // Update the lower bound as the right node is traversed
        if(! helper(root.right, root.val, upper))return false;


        return true;
    }
Copy the code

In the sequence traversal

You can also take advantage of binary search trees, where the middle order traversal elements are increasing. So you only need to walk through the binary search tree in middle order, and then check if the result of the walk is increasing.

The code is as follows:

    Integer max = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        if(! isValidBST(root.left))return false;
        
        // Update the current maximum value
        if(max ! =null && root.val <= max) return false;
        max = root.val;

        if(! isValidBST(root.right))return false;
        return true;
    }
Copy the code

conclusion

Recursion is a bit harder to understand, but with a lot of practice you can develop recursive thinking.

Here I would like to share teacher Qin Chao’s recursive code template. When writing recursion, we need to make these parts clear first.

    public void recursion(int level, int param) {
        // terminator is a recursive exit
        if (level == 100) return;

        // process processes logic
        param = 1;

        // Drill down
        recursion(level + 1, param);
        
        // Reverse States If necessary, the current layer state needs to be cleared
        param = 0;
    }
Copy the code

After proficiency, I believe you can also achieve a recursive shuttle. If you find this article helpful, please leave a comment and like it.