This article will share the solution ideas and steps of LeetCode question 98 in detail, hoping to bring help to you.

preface

Binary tree is a very important data structure. It involves a wide range of algorithms. Whether it is an amazing backtracking algorithm or an amazing dynamic programming, it is closely related to binary tree, which shows its importance.

I have little talent and learning. If you have any mistakes, please contact me to correct them. Thank you in advance.

1, Title Description

Give you the root node of a binary tree, root, to determine whether it is an effective binary search tree.

Valid binary tree:
The value of the left subtree of the node is less than that of the node, and the value of the right subtree of the node is greater than that of the node. Of course, the left subtree and the right subtree must also be binary search trees.

Example:

2, Detailed description of problem solving ideas and methods

1. Problem solving ideas

We find that the middle order traversal results of the binary search tree are increasing, that is, if the binary tree given by the topic is a binary search tree, the middle order traversal results will also conform to the increasing formula. Therefore, we can use the property of middle order ergodic to judge it and get a conclusion.
For the middle order traversal of binary search tree, you can check it in my blog: Blog address

2. Method details

Let's take the title example:

We can see that the middle order traversal result of the binary tree in the figure above is not incremental, so we can judge that the binary tree is not a binary search tree.

The code is as follows (example):

3, Code implementation

Python code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack, inorder = [], float('-inf')
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # If the value of the node obtained by the middle order traversal is less than or equal to the previous inorder, it indicates that it is not a binary search tree
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right

        return True

C + + Code:

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

C language code: This code comes from this

bool isValidBST_Helper(struct TreeNode* root, double min, double max) {
    if (root == NULL) {
        return true;
    }

    if (root->val <= min || root->val >= max) {
        return false;
    }

    return isValidBST_Helper(root->left, min, root->val) && isValidBST_Helper(root->right, root->val, max);
}

bool isValidBST(struct TreeNode* root) {
    return isValidBST_Helper(root, LONG_MIN, LONG_MAX);
}

Java code: This code comes from this

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // Access left subtree
        if (!isValidBST(root.left)) {
            return false;
        }
        // Accessing the current node: if the current node is less than or equal to the previous node traversed in the middle order, it indicates that the BST is not satisfied, and false is returned; Otherwise, continue traversal.
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // Access right subtree
        return isValidBST(root.right);
    }
}

summary

This concludes the sharing of this question. If you have any questions, please comment and point out. Finally, thank Momo for his patient company and waiting.