首页 > 代码库 > 【LeetCode】Validate Binary Search Tree

【LeetCode】Validate Binary Search Tree

2024-07-03 23:55:25   225人阅读

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.
package com.leetcode.ValidateBinarySearchTree;

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        boolean left=false;
        boolean right=false;
        if(root.left!=null){
            if(isLeftValid(root.left,root.val))
                left = isValidBST(root.left);
        }else{
            left=true;
        }
        if(root.right!=null){
            if(isRightValid(root.right,root.val))
                right = isValidBST(root.right);
        }else{
            right=true;
        }
        return left&&right;
    }

    private boolean isRightValid(TreeNode right, int val) {
        
        if(right!=null){
            if(right.val<=val)
                return false;
            return isRightValid(right.left,val)&&isRightValid(right.right, val);
        }else{
            return true;
        }
        
    }

    private boolean isLeftValid(TreeNode left, int val) {
        if(left!=null){
            if(left.val>=val)
                return false;
            return isLeftValid(left.left,val)&&isLeftValid(left.right, val);
        }else{
            return true;
        }
        
    }

    
}

 


联系
我们