LeetCode 98 Validate Binary Search Tree

标签: 二叉搜索树 LeetCode 发布于:2022-02-07 13:34:30 编辑于:2022-02-07 13:37:07 浏览量:338

概述

https://leetcode.com/problems/validate-binary-search-tree/

递归法

这里要注意的是,左右子树合法不代表其一定合法,root 的值还必须满足大于左子树的最大值,小于右子树的最小值。

另外还要注意题目的输入范围,用 INT_MIN 和 INT_MAX 不行。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LLONG_MIN, LLONG_MAX);
    }
    
    bool helper(TreeNode* root, long minV, long maxV) {
        if (!root) return true;
        if (root->val >= maxV || root->val <= minV) return false;
        return helper(root->left, minV, root->val) && helper(root->right, root->val, maxV);
    }
};

要是题目不给输入范围怎么办?实际上可以使用 TreeNode 来存,如果为 nullptr 的话就不检查该边界就好。

附上两年前的 Java 解法:

class Solution {
    private int last;
    private boolean isFirst;
    public boolean isValidBST(TreeNode root) {
        last = Integer.MIN_VALUE;
        isFirst = true;
        return helper(root);
    }
    
    private boolean helper(TreeNode node){
        if(node==null){
            return true;
        }
        if(node.left!=null){
            if(!helper(node.left)){
                return false;
            }
        }
        if(node.val<=last){
            if(isFirst){
                isFirst = false;
                last = node.val;
            }else{
                return false;
            }
        }else{
            if(isFirst){
                isFirst = false;
            }
            last = node.val;
        }
        if(node.right!=null){
            if(!helper(node.right)){
                return false;
            }
        }
        return true;
    }
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/