LeetCode :: Validate Binary Search Tree[具体分析]

LeetCode :: Validate Binary Search Tree[具体分析]

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

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.
回想一下BST的定义,任一节点的子孙分别递归满足。左子孙小于该节点,右子孙大于该节点。仅仅要推断这个就OK了;
一个主意点:在递归程序里面。仅推断一个节点大于左儿子小于右儿子是不够的,这样对于左儿子的右儿子以及右儿子的左儿子的
错误推断不到,因此须要将节点值变为边界值,递归下传;
代码例如以下:

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return check(root, INT_MIN, INT_MAX);
    }
    
private:
    bool check(TreeNode *root, int left, int right){
        if(root == NULL)
            return true;
        return (root->val > left) && (root->val < right) 
               && check(root->left, left, root->val) &&check(root->right, root->val, right); 
    }//这里的左儿子的左界用上面传下来的,右界用节点值,右儿子镜面对称
};


PS:依照注意点提到的思路写的
错误
代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (root == NULL)
            return true;
            
        bool bleft = true, bright = true;
        if (root->left != NULL){
            if (root->val > root->left->val){    //注意这里检验以及递归是不能保证根节点大于左边全部的。矛盾在于,左儿子的右儿子,以及右儿子的左儿子。
                bleft = isValidBST(root->left);
            }
            else{
                return false;
            }
        }
        
        if (root->right != NULL){
            if (root->val < root->right->val){
                bright = isValidBST(root->right);
            }
            else{
                return false;
            }
        }
        return bleft && bright;
    }
};


版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117593.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 半正定矩阵小计

    半正定矩阵小计抄录自百度百科定义:设A是n阶方阵,如果对任何非零向量X,都有X'AX>=0,就称A为半正定矩阵性质:1.半正定矩阵的行列式是非负的。2.半正定矩阵+半正定矩阵还是半正定矩阵

  • 关于Navicat ER图「建议收藏」

    关于Navicat ER图「建议收藏」今天给大家分享一个关于NavicatER图使用的小技巧,这里以NavicatforMySQL10.1.7为例。首先说一下ER图在哪里打开点击“查看”,选择“ER图表”这时就可以显示你建好的各个表了。虽然加了外键,但是显示不是很清晰,怎么办?在NavicatforMySQL界面的左下角有一个刷新按钮点击后,即可生成关系明确的ER图了如果点击刷新后仍没反应,请点击“重新…

  • R语言画图时常见问题

    各位朋友,我已开通微信公共号:小程在线我会把文章及时的更新到公共号上,欢迎大家的关注。1如何在同一画面画出多张图?修改绘图参数,如par(mfrow=c(2,2))或par(mfcol=c(2,2));par():mar设置图离四个边缘的距离;bg设置背景颜色;xaxt和yaxt设置坐标轴标签的类型(=”n”表示不画轴标签);xlim和ylim设置坐标轴的范围…

  • mp4 avc格式_sps_pps[通俗易懂]

    mp4 avc格式_sps_pps[通俗易懂]http://blog.csdn.net/sunnylgz/article/details/7680203

    2022年10月17日
  • navicat premium mac 激活码【最新永久激活】

    (navicat premium mac 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 框架结构和砖混结构的区别_react框架官网

    框架结构和砖混结构的区别_react框架官网实现:创建四个组件,分别是头组件,尾组件,list组件,item组件,存在于这个mvc中的。在APP.js中分别引入前三个个组件(item组件是存在于list中的,所以在list中引入item组件)在app.js中写好初始数据,在list中显示出来const{todos}=this.propsreturn(<ul>{todos.map(todo=>{return<Itemkey={

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号