98. Verify binary search tree (medium binary search tree DFS)

98. Verify binary search tree

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

It works The binary search tree is defined as follows ：

The left subtree of the node contains only Less than Number of current nodes .
The right subtree of the node contains only Greater than Number of current nodes .
All left and right subtrees themselves must 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
explain ： The value of the root node is 5 , But the value of the right child node is 4 .

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/validate-binary-search-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Need to understand the properties of binary search tree ： If the left subtree of the binary tree is not empty , Then the values of all nodes on the left subtree are less than the values of its root nodes ; If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of its root node ; Its left and right subtrees are also binary search trees .
We can design a recursive function helper(root, lower, upper) To judge recursively , Function means to consider with root Root subtree , Determine whether the values of all nodes in the subtree are in (lower, upper) Within the scope of . If root The value of the node val be not in (lower, upper) If the condition is not satisfied, return directly , Otherwise, we need to continue to call recursively to check whether the left and right subtrees satisfy , If they are satisfied, it means that this is a binary search tree .
So according to the properties of the binary search tree , When the left subtree is called recursively , We need to put the upper bound upper Change it to root.val, That is to call helper(root.left, lower, root.val), Because the value of all nodes in the left subtree is less than the value of its root node . Similarly, when the right subtree is called recursively , We need to put the lower bound lower Change it to root.val, That is to call helper(root.right, root.val, upper).

Answer key （Java）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public boolean isValidBST(TreeNode root) {
    
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode root, long lower, long upper) {
    
        if (root == null) {
    
            return true;
        }
        if (root.val <= lower || root.val >= upper) {
    
            return false;
        }
        return dfs(root.left, lower, root.val) && dfs(root.right, root.val, upper);
    }
}