98. Validate Binary Search Tree

发布时间：2020-12-14 03:49:19 所属栏目：大数据来源：网络整理

导读：/** * 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) { return helper(root,Long.MIN_

/**
 * 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) {
      return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean helper(TreeNode root,long minval,long maxval){
      if(root == null) return true;
      if(root.val >= maxval || root.val <= minval) return false;
      return helper(root.left,minval,root.val) && helper(root.right,root.val,maxval);
        
    }
}

Given a binary tree,determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys?less than?the node‘s key.
The right subtree of a node contains only nodes with keys?greater than?the node‘s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   /   1   3
Output: true

Example 2:

    5
   /   1   4
?    / ?   3   6
Output: false
Explanation: The input is: [5,1,4,null,3,6]. The root node‘s value
?            is 5 but its right child‘s value is 4.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!