【Leetcode】98. 验证二叉搜索树

nidaye 发布于2019-08-16 15:10 / 2597人阅读

摘要：题目给定一个二叉树，判断其是否是一个有效的二叉搜索树。所有左子树和右子树自身必须也是二叉搜索树。题解这道题目主要是利用二叉搜索树的一个性质二叉搜索树的中序遍历结果是一个升序的序列。

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / 
  1   3
输出: true

示例 2:

输入:
    5
   / 
  1   4
     / 
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

这道题目主要是利用二叉搜索树的一个性质：
二叉搜索树的中序遍历结果是一个升序的序列。
那么问题转变成：中序遍历 + 验证是不是升序.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List inPrint(TreeNode root, List res) {
        if (root != null) {
            inPrint(root.left, res);
            res.add(root.val);
            inPrint(root.right, res);
        }
        return res;
    }
    
    public boolean isValidBST(TreeNode root) {
        List res = inPrint(root, new LinkedList<>());
        if (res.size() == 1) {
            return true;
        }
        for (int i = 1; i < res.size(); i++) {
            if (res.get(i) <= res.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

GPU云服务器云服务器二叉树排序树规则二叉查找树二叉排序树二叉树遍历

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

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

LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

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

用户84 2019-08-23 17:12 评论0 收藏0
通过几道题目学习二叉搜索树

摘要：根据这个特征，用二分法来将有序数组转换为一颗二叉搜索树。边界条件向下取整得到中间值递归二分法接下来我们验证下一棵树是否满足二叉搜索树。二验证二叉搜索树相关题目验证二叉搜索树中等思路就是，中序遍历如果满足递增的就行。二叉树大家都知道，二叉搜索树满足以下特征：节点的左子树只包含小于当前节点的数节点的右子树只包含大于当前节点的数所有左子树和右子树自身必须也是二叉搜索树二叉搜索树也叫...

Steven 2019-08-23 13:42 评论0 收藏0
Leetcode打卡——二叉搜索树（共8题）

摘要：也就是说，有个节点的平衡二叉搜索树，它的高度是。以搜索操作为例，如果二叉搜索树的高度为，则时间复杂度为。二叉搜索树的高度的确很重要。树集合，中的或者中的，是由高度平衡的二叉搜索树实现的。 ...

Olivia 2021-11-15 11:38 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论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