作为一名数据结构与算法的新手，碰到二叉树和迭代的问题时，总是一头雾水，现在就总结一些方法。
迭代问题应该抓住几个关键点
1.函数的输入是什么？
2.函数的返回是什么？
3.将主体可以划分为哪些迭代部分，怎样构成？
4.什么条件下才能进入迭代（有时理解为何时中止迭代更方便）？
5.如何架构整个程序？
class Solution:
def VerifySquenceOfBST(self, sequence):
针对剑指offer的这个题目，来一步步分析。
1.函数的输入是什么？
根据题目和函数入口可以看到，输入是数组。由此可以确定，在迭代中的输入也是数组，因此我们要想进行迭代，就需要划分出进入迭代的数组。
2.函数的返回是什么？
根据题目的要求，返回bool类型，则根据迭代，我们需要前半段和后半段都是True时最终才回返回True。假设用left来接收做半段的返回结果，right来返回右半段的返回结果，当左右都为True时，最终才能确定这是一课二叉搜索树，因此函数的最终应该返回
return left and right
3.将主体可以划分为哪些部分？
以[5,7,6,9,11,10,8]为例，首先找出根节点8.若不存在，则直接返回False，则有
if not sequence：
return False
然后根节点的左子树的值应该全部小于8，右子树的值应该全部大于8，则通过算法划分出前半段为l = [5,7,6]，后半段为r = [9,11,10]
但是这只是迭代函数的输入，我们用第二部分析得到的left = self.VerifySquenceOfBST([5,7,6]) ,right = self.VerifySquenceOfBST([9,11,10])来接收迭代函数的返回值，且当left 和right均为True时，函数才返回True
4.什么条件下才能进入迭代
最基本的是列表不能为空，这里在3中已经判断了，仔细观察，迭代函数的输入应该是子树，因此当我们通过算法划分出了片段之后，我们要确保左子树和右子树的元素大于等于两个才能进入迭代。（在前面我们已经通过算法合理划分出左右了，因此当左或右只有一个或没有元素时虽然不进入迭代，但值也为True），所以先直接令left = True ,right = True,再分别进入判断是否应该进入迭代，进入迭代，则用left和right接收迭代值。
5.如何架构整个程序？
算法的主题是，先找出根节点，再从数组开头遍历，找到第一个大于根节点的位置，设为切分点。此时左边数组中的均小于root无须判断，对右边进行遍历，假设出现一个小于root的值，则直接返回False.
整个流程下来就是：
1.判断列表是否为空，若为空则直接返回False，这里容易产生一个令人疑惑的点，就是左节点就是空的，而右子树满足条件，整棵树满足二叉搜索树，然而False and True不是False吗？这样就输出错误了，因此我们在设置进入迭代条件的时候就要使得子树长度大于等于2才能进入迭代，这在后面写。
2.开始按照上面的方法切割出左右子树。
3.当左，右子树个数小于等于1的时候，是满足条件的，因此直接令left 和 right的值等于True，且不进入迭代；否则进入迭代，用left和right获取迭代值。
4.最终返回结果。
#coding:utf-8
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
#判断sequence是否为空，这是对最原始的数组进行判断
if not sequence:
return False
#先找到根节点，然后随便初始化切割点的数值
root = sequence[-1]
split = len(sequence)-1
#开始切割数组
for index,item in enumerate(sequence[:-1]):
if item > root:
split = index
break
#切割好数组后，前段不用判断，只需判断后半段，只要出现一次小于root的值，就直接返回False
for item in sequence[split:-1]:
if item <root:
return False
#开始判断left和right的值，分为进入迭代和不进入迭代两种情况
left = True
if len(sequence[:split])> 1:
left = self.VerifySquenceOfBST(sequence[:split])
right = True
if len(sequence[split:-1]) >1:
right = self.VerifySquenceOfBST(sequence[split:-1])
return left and right
网友评论