leetcode - [98] Validate Binary Search Tree

2020/06/18

问题描述

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

判断一棵二叉树是否为有效的二叉搜索树。

举个例子:

解法1

我的想法是这样的:

首先,我需要两个全局变量。

一个用来存储最终结果ans,另一个用来存储上一个节点的值pre

这里有个小技巧,由于第一个节点没有前置节点,

所以我们可以将pre的数据类型设置为Integer,并将其初始值设置为null

然后,进行前序递归遍历,不断将当前元素的值curpre进行比较,

cur <= pre,则说明它不是有效的BST

来看下实现:

class Solution {
    
    boolean ans = true;
    Integer pre = null;
    
    public boolean isValidBST(TreeNode root) {
        
        inorder(root);
        return ans;
    }
    
    private void inorder(TreeNode root){
        
        if (root == null) return;
        
        inorder(root.left);
        
        int val = root.val;
        if (pre != null){
            if (val <= pre){
                ans = false;
                return;
            }
        }
        pre = val;
        
        inorder(root.right);
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory