剑指offer 面试33题
2024-08-29 02:08:21
面试33题:
题:二叉搜索树的后序遍历序列
题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路:递归
解题代码:
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence or len(sequence)<=0:
return False
root=sequence[-1]
i=0 #找出左小右大的分界点i,此时i属于右子树
for node in sequence[:-1]:
if node > root:
break
i+=1 #如果在右子树中有比根节点小的值,直接返回False
for node in sequence[i:-1]:
if node < root:
return False
#判断左子树是否为二叉搜索树
left=True
if i>0:
left=self.VerifySquenceOfBST(sequence[:i])
#判断右子树是否为二叉搜索树
right=True
if i<len(sequence)-1:
right=self.VerifySquenceOfBST(sequence[i:-1]) return left and right
最新文章
- 在js中获取在css中设置的background-image值
- iOS 学习 - 24 全局跑马灯,支持后台回到前台
- NBUT 1535
- Vue+Webpack+Grunt集成
- C# 生成中间含有LOGO的二维码
- DIV JS CSS 轻量级弹出层 兼容各浏览器
- Dagger学习笔记
- 1 对WinMain的理解
- linux下查看本机socket端口详细信息
- javascript对象属性——数据属性和访问器属性
- Android 省市县 三级联动(android-wheel的使用)
- 剑指Offer-数组中重复的数字
- dex分包方案
- TLS详解
- Java基础17:Java IO流总结
- java代码的编译执行过程
- gitlab 可以上传代码,但是 不能 上传 tag 问题
- [work]Spring_Jdbc
- Linux常用的20个命令
- 一步步教你编写不可维护的 PHP 代码
热门文章
- Atitit.&#160;Ati&#160;IDE&#160;开发平台的第一版规划
- 基于RocketIO的高速串行协议设计与实现
- Codeforces Round #277 (Div. 2)---A. Calculating Function (规律)
- SpringBoot+MybatisPlus(多数据源和主从分离)
- 使用Charles对Https请求进行抓包
- Python、Lua和Ruby之优劣
- Anaconda+Tensorflow环境安装与配置(转载)
- YII安装步骤(windows)
- Eclipse 创建 Java 包
- 模式识别之概率分布---平均分布,正态分布,一阶滑动和,一阶线性回归 C语言编程