[LeetCode] 二叉搜索树判定

妖狐艹你老母 2022-05-18 10:11 192阅读 0赞

# 出处 #

> [验证二叉搜索树][Link 1]

# 分析 #

> 给定一个二叉树，判断其是否是一个有效的二叉搜索树。  
> 假设一个二叉搜索树具有如下特征：  
> \- 节点的左子树只包含小于当前节点的数。  
> \- 节点的右子树只包含大于当前节点的数。  
> \- 所有左子树和右子树自身必须也是二叉搜索树。

中序遍历即：左中右 并把遍历节点依次放在列表中就能保证列表从小到大排列。因此检验最终的列表即可。

# 结果 #

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            List<Integer> list = new LinkedList<Integer>();
            mid(root, list);
            if(list.size() < 1) {
                return true;
            }
    
            int first = list.get(0);
            for(int i=1;i<list.size();i++) {
                if(list.get(i) <= first) {
                    return false;
                }
                first = list.get(i);
            }
    
            return true;
        }
    
        private void mid(TreeNode node, List<Integer> list) {
    
            if(node != null) {
                mid(node.left,list);
                System.out.println(node.val);
                list.add(node.val);
                mid(node.right,list);
            }
        }
    
    }

[Link 1]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/48/

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 99. 恢复二叉搜索树

中序遍历，弄在数组里面，再弄个数组复制一份排好序比较哪里错了，换回来中序遍历的时候用map存一下数字的地址（默认没有重复元素） class Solutio

港控/mmm°/ 2023年06月08日 03:19/ 0 赞/ 94 阅读

相关 LeetCode 98. 验证二叉搜索树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

青旅半醒/ 2022年11月05日 08:44/ 0 赞/ 159 阅读

相关【LeetCode】二叉树问题：二分搜索树

二分搜索树 [235. 二叉搜索树的最近公共祖先][235.] 难度简单532收藏分享切换为英文接收动态反馈给定一个二叉搜索树, 找到该树中两个指定节点的最近公

快来打我*/ 2022年10月29日 09:12/ 0 赞/ 190 阅读

相关 leetcode 669 修剪二叉搜索树

前言题目：[669. 修剪二叉搜索树][669.] 参考题解：[修剪二叉搜索树-力扣官方题解][-] -------------------- 提交代码看

╰+攻爆jí腚メ/ 2022年09月12日 08:49/ 0 赞/ 149 阅读

相关 Leetcode 98. 验证二叉搜索树

题目重述给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节

悠悠/ 2022年09月09日 11:48/ 0 赞/ 171 阅读

相关 [LeetCode] 二叉搜索树判定

出处 > [验证二叉搜索树][Link 1] 分析 > 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 > 假设一个二叉搜索树具有如下特征： > \-

妖狐艹你老母/ 2022年05月18日 10:11/ 0 赞/ 193 阅读

相关 LeetCode98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。

爱被打了一巴掌/ 2022年05月10日 23:03/ 0 赞/ 165 阅读

相关【LeetCode】98. 验证二叉搜索树

题目链接：[https://leetcode-cn.com/problems/validate-binary-search-tree/description/][https_l

小鱼儿/ 2022年05月03日 00:56/ 0 赞/ 185 阅读

相关二叉搜索树判定方法（c++实现）

[二叉搜索树判定方法（c++实现）][c] \--- 欢迎指正--- 自己想到的方法是：使用中序遍历数组或者链表，然后比较数组或者链表中的数据是否有序。 CC150

一时失言乱红尘/ 2022年02月28日 08:16/ 0 赞/ 198 阅读

相关 leetcode【98】验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所

太过爱你忘了你带给我的痛/ 2021年10月03日 01:36/ 0 赞/ 267 阅读