leetcode98. Validate Binary Search Tree

codercao 发布于2019-08-15 10:56 / 3034人阅读

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。

题目要求

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:
    2
   / 
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / 
  2   3
Binary tree [1,2,3], return false.

检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。

思路一：stack 深度优先算法

如果了解中序遍历的同学可以知道，一颗二叉查找树的中序遍历结果应当是一个数值有小到大递增的数组。正因为中序遍历是指先遍历左子树，接着遍历中间节点，再遍历右子树，恰好和查找树的值递增顺序相同。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。代码如下：

    public boolean isValidBST(TreeNode root) {
        long currentVal = Long.MIN_VALUE;
        LinkedList stack = new LinkedList();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val<=currentVal) return false;
            currentVal = root.val;
            root = root.right;
        }
        return true;
    }

这里需要注意的是，将最小值取为Long.MIN_VALUE，以免出现Integer.MIN_VALUE的误判

思路二：递归深度优先算法

我们知道，任何一个二叉查找树的节点都有一个取值区间，如果我们能够找到该节点的取值区间以及其左右子节点对应的取值区间，就可以递归的判断该树是否是一颗二叉查找树。为了实现递归，我们需要找到其中的一般情况。假设我们已经知道了当前节点的区间，那么左子节点的上限即为父节点的值，而下限则应该为父节点的下限。同理，右子节点的下限是父节点的值，而上限也就是父节点的上线。
代码如下:

    public boolean isValidBST2(TreeNode root){
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValid(TreeNode treeNode, long lowerBound, long upperBound){
        if(treeNode==null) return true;
        if(treeNode.val>=upperBound || treeNode.val<=lowerBound) return false;
        return isValid(treeNode.left, lowerBound,treeNode.val) && isValid(treeNode.right, treeNode.val, upperBound);
    }

云服务器 GPU云服务器 binary-search-tree binary-tree binary-search Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67433.html

leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。思路一可以看到，对二叉查找树的中序遍历结果应当是一个递增的数组。这里我们用堆栈的方式实现中序遍历。题目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...

songze 2019-08-15 10:56 评论0 收藏0
[Leetcode] Validate Binary Search Tree 验证二叉搜索树

摘要：注意这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了和，所以要在递归之前先判断是否符合和的条件。代码如果该节点大于上限返回假如果该节点小于下限返回假递归判断左子树和右子树 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

fuchenxuan 2019-08-14 12:40 评论0 收藏0
[LeetCode] Largest BST Subtree

Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all ...

Youngdze 2019-08-14 14:55 评论0 收藏0
LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用户84 2019-08-23 17:12 评论0 收藏0