lintcode95. 验证二叉查找树

缺乏、安全感 2023-07-03 08:26 3阅读 0赞

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

节点的左子树中的值要严格小于该节点的值。  
节点的右子树中的值要严格大于该节点的值。  
左右子树也必须是二叉查找树。  
一个节点的树也是二叉查找树。

样例
    样例 1:
    
    输入：{
        -1}
    输出：true
    解释：
    二叉树如下(仅有一个节点）:
    	-1
    这是二叉查找树。
    样例 2:
    
    输入：{
        2,1,4,#,#,3,5}
    输出：true
    解释：
    	二叉树如下：
    	  2
    	 / \
    	1   4
    	   / \
    	  3   5
    这是二叉查找树。

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param root: The root of binary tree.
         * @return: True if the binary tree is BST, or false
         */
        bool isValidBST(TreeNode * root) {
        
            // write your code here
            vector<int> tmp;
            tree(root,tmp);
            for (int i = 1; i < tmp.size(); i++) {
        
                /* code */
                if(tmp[i]<=tmp[i-1]) return false;
            }
            return true;
        }
        void tree(TreeNode*root,std::vector<int> &tmp)
        {
        
            if(root==NULL) return;
            tree(root->left,tmp);
            tmp.push_back(root->val);
            tree(root->right,tmp);
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 lintcode 164. 不同的二叉查找树 II

给出n，生成所有由1…n为节点组成的不同的二叉查找树样例样例 1: 输入:3 输出: 1 3

深藏阁楼爱情的钟/ 2023年07月07日 12:39/ 0 赞/ 10 阅读

相关 lintcode95. 验证二叉查找树

给定一个二叉树，判断它是否是合法的二叉查找树(BST) 一棵BST定义为：节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右

缺乏、安全感/ 2023年07月03日 08:26/ 0 赞/ 4 阅读

相关 leetcode——二叉树、二叉查找树

leetcode——二叉树、二叉查找树 104. 二叉树的最大深度 111. 二叉树的最小深度 226. 翻转二叉树

r囧r小猫/ 2022年09月05日 12:39/ 0 赞/ 224 阅读

相关不同的二叉查找树 II lintcode

给出n，生成所有由1...n为节点组成的不同的二叉查找树您在真实的面试中是否遇到过这个题？ Yes 样例给出n = 3，生成所有5种不同形态的二叉查找树：

雨点打透心脏的1/2处/ 2022年07月16日 09:55/ 0 赞/ 150 阅读

相关二叉查找树

本文将会介绍一种能够将链表插入的灵活性和有序数组查找的高效性结合在一起的符号表实现。定义一颗二叉查找树（BST）是一颗二叉树，其中每个结点都含有一个Comparab

布满荆棘的人生/ 2022年07月16日 00:22/ 0 赞/ 205 阅读

相关【LintCode 简单】85. 在二叉查找树中插入节点

1.问题描述：给定一棵二叉查找树和一个新的树节点，将节点插入到树中。你需要保证该树仍然是一棵二叉查找树。 2.样例：给出如下一棵二叉查找树，在插入节点6

向右看齐/ 2022年06月01日 03:18/ 0 赞/ 195 阅读

相关二叉树（四）---查找二叉树

上次我说了如何去遍历一棵二叉树，今天我来说一说查找二叉树是怎样实现的。首先我来介绍一下查找二叉树是怎样生成的。这个是我为我的二叉树设置的一些基础的组成数据结构

深碍√TFBOYSˉ_/ 2022年05月25日 09:37/ 0 赞/ 249 阅读

相关【lintcode】删除二叉查找树的节点

描述给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。

Bertha 。/ 2022年05月20日 07:58/ 0 赞/ 205 阅读

相关二叉查找树

<table> <tbody> <tr> <td> <p>package 树;</p> <p>import java.util.Stack;</p> <p>/

我就是我/ 2022年05月13日 01:40/ 0 赞/ 250 阅读

相关二叉查找树

理解在二叉树的基础上，假设一个节点值都为Integer类型，现在有一个节点A，那么A的左子树中的所有值一定小于A节点的值，A的右子树中的所有值一定大于A的节点的值，如果

清疚/ 2021年09月11日 06:56/ 0 赞/ 509 阅读