当前位置: 首页 > article >正文

判断是不是二叉搜索树(C++)

目录

1 问题描述

1.1 示例1

1.2 示例2

2 解题思路

3 代码实现

4 代码解析

4.1 中序遍历函数 inorder

4.2 主函数 isValidBST 初始化及中序遍历调用 

4.3 检查数组中元素是否严格递增

4.4 返回验证结果 

5 总结


1 问题描述

给定一个二叉树根节点,请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

例:

图1

图2

数据范围:节点数量满足 1≤n≤104 1≤n≤104  ,节点上的值满足 −231≤val≤231−1 −231≤val≤231−1 

1.1 示例1

输入:

{1,2,3}

返回值:

false

说明:

如题面图1 

1.2 示例2

输入:

{2,1,3}

返回值:

true

说明:

如题面图2 

2 解题思路

首先利用二叉搜索树中序遍历后节点值为升序的特点,将树中的所有节点通过中序遍历存入一个数组,然后遍历该数组检查是否严格递增。如果发现任意相邻两个数不满足前小于后的关系,则说明该树不是有效的二叉搜索树;否则,返回true证明该树满足BST的性质。

3 代码实现

    bool isValidBST(TreeNode* root) {
        // write code here
        vector<int> ans;
        inorder(root, ans);

        for(int i = 1; i < ans.size(); i++)
        {
            if(ans[i-1] > ans[i]) return false;
        }

        return true;
    }

    void inorder(TreeNode* node, vector<int> &ans) {
        if (node == nullptr) return;
        inorder(node->left, ans);
        ans.push_back(node->val);
        inorder(node->right, ans);
    }

4 代码解析

4.1 中序遍历函数 inorder

void inorder(TreeNode* node, vector<int> &ans) {
    if (node == nullptr) return;
    inorder(node->left, ans);
    ans.push_back(node->val);
    inorder(node->right, ans);
}

使用递归实现中序遍历(左-根-右)的方式遍历二叉树,将节点值依次存入传入的数组中。若当前节点为空,则直接返回,不做任何操作。

4.2 主函数 isValidBST 初始化及中序遍历调用 

bool isValidBST(TreeNode* root) {
    vector<int> ans;
    inorder(root, ans);
    // 后续验证步骤

 首先定义一个空的数组 ans,然后调用 inorder 函数对整个二叉树进行中序遍历,收集所有节点的值。

4.3 检查数组中元素是否严格递增

    for(int i = 1; i < ans.size(); i++) {
        if(ans[i-1] > ans[i]) return false;
    }

遍历存有节点值的数组 ans,依次比较相邻两个元素。由于二叉搜索树中序遍历结果应为严格递增,若前一个数大于后一个数,则说明该树不满足二叉搜索树的要求,立即返回 false

4.4 返回验证结果 

    return true;
}

如果遍历完数组没有发现逆序的情况,则说明所有节点值均满足严格递增的条件,函数最终返回 true,表示该树是一个有效的二叉搜索树。 

5 总结

本文总结了如何判断一棵二叉树是否为有效的二叉搜索树。文章首先描述了问题的要求,即左子树节点值需小于根节点、右子树节点值需大于根节点。接着,介绍了利用中序遍历特性(遍历结果为严格递增序列)来验证BST性质的方法:先通过递归中序遍历将节点值存入数组,再遍历数组检查是否严格递增。详细的代码实现和解析使读者能够清晰地理解整个解题思路和过程。


http://www.kler.cn/a/588667.html

相关文章:

  • Selenium 自动化测试学习总结
  • 不像人做的题————十四届蓝桥杯省赛真题解析(上)A,B,C,D题解析
  • 【鸿蒙开发】Hi3861学习笔记- GPIO之继电器
  • 时序约束整理
  • 【sklearn 03】逻辑回归、决策树、支持向量机
  • 网页制作16-Javascipt时间特效の设置D-DAY倒计时
  • 【Node.js入门笔记5---fs文件信息与元数据】
  • 项目经历-笔记
  • perl的package中“Subroutine new redefined”问题
  • (六)Spring Boot学习——spring security做基于方法的认证
  • IMX6ULL学习整理篇——UBoot的一些基础知识(1.编译流程)
  • 使用yolov8+flask实现精美登录界面+图片视频摄像头检测系统
  • 电机控制常见面试问题(十一)
  • 【CSS】一、基础选择器
  • 蓝桥杯好题推荐---激光炸弹
  • 【蓝桥杯每日一题】3.16
  • 【Agent】OpenManus 项目架构分析
  • 技术栈分享之----Swagger
  • 专题|Python贝叶斯金融数据应用实例合集:随机波动率SV模型、逻辑回归、参数更新、绩效比较BEST分析亚马逊股票、普尔指数...
  • 思维训练让你更高、更强 |【逻辑思维能力】「刷题训练笔记」假设法模式逻辑训练题(6-16)