数据结构的树
题目
给予一个二叉树的根节点,验证该树是否是二叉树搜索树,在O(n)时间内。
分析与解答
二叉搜索树是一种特殊的二叉树
它满足如下的条件:
- 结点的左子树所有结点的值都小于等于该结点的值。
- 结点的右子树所有结点的值都大于该结点的值。
- 结点的左右子树同样都必须是二叉搜索树。
也就是说
- 任何一个节点的key值都比它左子树上的节点的key值要大,但是比它右子树上的key值要小。
- 节点查找、插入、删除等操作的时间复杂度都是O(logn)
主要的一个特点 就是中序遍历一棵树 会得到一个递增的序列
在此题目的条件是給出一个根节点
简化起见 考虑简单的情况
即是給出的二叉树形式为列表的形式 顺序为前序 也就是一个元素就是根节点
比如
[5,1,4,#,#,3,6] 这个是給出的二叉树 根节点为第一个元素 也就是5
注意一下 实际上在 python 当中給出的应该是这样的列表
[5, 1, 4, None, None, 3, 6]
1 | def traverse_binary_tree(node, callback): |
解法
1 | class Solution1(object): |
另外也可以依次比较左右子树各个子节点的值 保证 左 < zhong < 右
1 | class Solution2(object): |
工程化的项目当中 一般是测试先行 也就是说需要先把测试用例这些东西准备好
在此 为了完善起见 肯定是需要补上测试用例的
能跑过测试 说明代码是正确的
1 | class Node(object): |
首先可以运行tests.py 文件 里面暂时只放了6个测试用例 可以看到是通过的
本次 运行环境为 python3.5
当然工程环境下可能有上百个以上的测试用例