#一人分享一道面试手撕题#【题目来源】
公司/部门:腾讯-微信支付后台开发
面试轮次:二面
考察形式:共享屏幕现场编写

【原题描述】
实现一个函数,用于验证二叉搜索树(BST)的有效性。
给定二叉树根节点,判断该树是否是有效的二叉搜索树。
有效BST定义为:
- 左子树所有节点值 < 当前节点值
- 右子树所有节点值 > 当前节点值
- 左右子树也必须是BST

示例:
输入:[5,1,4,null,null,3,6]
输出:false(根节点5的右子树中包含值3,小于5)
要求:时间复杂度尽可能优

【面试官关注点】

是否理解BST的本质定义(不仅是左右孩子大小关系)
能否想到利用上下界递归验证的思路
边界条件处理:空树、int边界值、重复值处理
代码简洁性和变量命名可读性
全部评论
好难啊 不愧是大佬
点赞 回复 分享
发布于 01-11 17:03 陕西

相关推荐

2025-12-31 19:36
已编辑
哈尔滨工业大学(威海) C++
一面&nbsp;12.2340&nbsp;分钟,刚面完官网马上就通过了,手撕第二道题想半天想不出来,面试官给了提示马上写出来了。鹅的面试官非常和蔼,全程笑着面完的,面试之前非常焦虑紧张,对自己的项目不是很熟悉,面试内容没怎么问项目,都是八股和算法,体验很好。面试问到的内容:值传递和引用传递提到了右值,什么时候用右值Unordered_map&nbsp;和&nbsp;map&nbsp;的区别Auto&nbsp;用过吗,什么时候用,有什么风险多继承有什么问题,菱形继承怎么解决虚函数表的原理C++&nbsp;怎么新建线程两个线程操纵一个变量会怎么样栈和堆了解吗,有什么区别程序编译运行过程发生了什么Static&nbsp;的函数有了解吗Const&nbsp;和&nbsp;constexpr字符的子串、旋转升序数组找最小值(二分查找)反问环节:部门做什么、后续流程IEG&nbsp;给王者等游戏提供工具优化、给公司其他部门提供工具。二面流程和一面差不多,不用太担心。二面&nbsp;12.2970&nbsp;分钟,一面面试官说二面和一面差不多让我别太担心,结果完全不是,一上来就问底层原理,操作系统给我拷打懵了,感觉啥也不会,虽然面试官给我解释然后让我重新答一遍,可我真的想不出来。面试问到的内容:看到你这个奖项,美赛得了什么奖?ACM&nbsp;打过吗?Elf&nbsp;有了解吗?虚拟地址和物理地址如何转换?快表的缩写是什么?如果查找从内存中查找一个数据,查到以后放到多级缓存中,放到哪一级?Linux&nbsp;中命令行定位搜索文件中的某个字符串在哪个文件静态链接和动态链接有了解吗?如果在一个&nbsp;h&nbsp;文件中定义一个类,然后在&nbsp;B、C&nbsp;中写这个类,有影响吗?如何避免头文件的重复调用?汇编文件了解吗?如何把分配在栈和堆中?别说这么多就说代码怎么写有两个线程,要分配一块空间,不加锁怎么实现(原子变量可行,面试官问不用原子变量如何实现)如果有一个类,里面只有一个&nbsp;int,然后他的子类是一个八字节的&nbsp;long&nbsp;long,这两个地址是挨着的吗?不是的话中间是什么?类型转换有了解吗?如果要把一个&nbsp;long&nbsp;long&nbsp;值转换为地址赋给指针要用什么?cmake了解吗?makefile会写吗?手撕:单调栈,几天后气温升高感觉不止这些,还问了很多,每个问题都追问得很细,想不起来了。不过确实都不怎么会,寒假得好好沉淀一下原理。
查看26道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-02 20:58
百度 后端 30x16 + 6位数qzf 硕士985
点赞 评论 收藏
分享
评论
2
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务