Python算法题集_验证二叉搜索树
- 题98:验证二叉搜索树
- 1. 示例说明
- 2. 题目解析
- - 题意分解
- - 优化思路
- - 测量工具
- 3. 代码展开
- 1) 标准求解【DFS递归】
- 2) 改进版一【DFS递归+终止检测】
- 3) 改进版二【BFS迭代+终止检测】
- 4. 最优算法
本文为Python算法题集之一的代码示例
题98:验证二叉搜索树
1. 示例说明
-
给你一个二叉树的根节点
root
,判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 1
2. 题目解析
- 题意分解
- 本题为二叉搜索树的验证
- 基本的设计思路是进行二叉树的中序遍历,基本的思路是深度优先算法【DFS(Depth-First Search)】、广度有限算法【BFS(Breadth-First Search)】
- 检查中序遍历的结果是否为有序的,如果有序就是二叉搜索树
- 优化思路
-
通常优化:减少循环层次
-
通常优化:增加分支,减少计算集
-
通常优化:采用内置算法来提升计算速度
-
分析题目特点,分析最优解
-
可以考虑采用DFS、BFS进行中序遍历
-
可以在过程中进行终止条件判断,减少不必要的遍历计算
-
- 测量工具
- 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
CheckFuncPerf
(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块- 本题本地化超时测试用例自己生成,详见【最优算法章节】
3. 代码展开
1) 标准求解【DFS递归】
先进行DFS递归求解,然后进行有序判断
马马虎虎,超过45%
import CheckFuncPerf as cfp
class Solution:
def isValidBST_base(self, root):
def inorderTraversal_dfs(root):
if not root:
return []
return inorderTraversal_dfs(root.left) + [root.val] + inorderTraversal_dfs(root.right)
list_node = inorderTraversal_dfs(root)
for iIdx in range(len(list_node)-1):
if list_node[iIdx] >= list_node[iIdx+1]:
return False
return True
aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 isValidBST_base 的运行时间为 317.15 ms;内存使用量为 112.00 KB 执行结果 = False
2) 改进版一【DFS递归+终止检测】
在DFS递归中进行终止检测
性能卓越,超过97%
import CheckFuncPerf as cfp
class Solution:
def isValidBST_ext1(self, root):
def inOrder(root, result):
if root == None:
return True
if inOrder(root.left, result) == False:
return False
if result and result[-1] >= root.val:
return False
result.append(root.val)
if inOrder(root.right, result) == False:
return False
return True
list_node = []
return inOrder(root, list_node)
aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 isValidBST_ext1 的运行时间为 12.99 ms;内存使用量为 8.00 KB 执行结果 = False
3) 改进版二【BFS迭代+终止检测】
采用堆栈实现BFS算法,在遍历过程中进行终止条件检测
性能优越,超过90%
import CheckFuncPerf as cfp
class Solution:
def isValidBST_ext2(self, root):
if not root:
return True
list_stack = []
list_node = []
while root or list_stack:
if root:
list_stack.append(root)
root = root.left
else:
curnode = list_stack.pop()
if list_node:
if curnode.val <= list_node[-1]:
return False
list_node.append(curnode.val)
root = curnode.right
return True
aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 isValidBST_ext2 的运行时间为 9.97 ms;内存使用量为 568.00 KB 执行结果 = False
4. 最优算法
根据本地日志分析,最优算法为第3种方式【BFS迭代+终止检测】isValidBST_ext2
iLen = 1000000
nums = [x for x in range(iLen)]
nums[499995], nums[50005] = nums[50005], nums[499995]
def sortedArrayToBST(nums):
if not nums:
return
mid = len(nums) // 2
root = TreeNode(nums[mid])
if mid == 0:
return root
root.left = sortedArrayToBST(nums[:mid])
root.right = sortedArrayToBST(nums[mid+1:])
return root
aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 算法本地速度实测比较
函数 isValidBST_base 的运行时间为 317.15 ms;内存使用量为 112.00 KB 执行结果 = False
函数 isValidBST_ext1 的运行时间为 12.99 ms;内存使用量为 8.00 KB 执行结果 = False
函数 isValidBST_ext2 的运行时间为 9.97 ms;内存使用量为 568.00 KB 执行结果 = False
一日练,一日功,一日不练十日空
may the odds be ever in your favor ~