二叉搜索树的后序遍历序列

问题描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。背景知识：
二叉搜索树（Binary Search Tree），又叫二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。算法描述：
将数列分为三段，最后一段是最后一个数，也是树的根；第一段小于根，第二段大于根：
| 小于根 | 大于根 | 根 |然后小于根和大于根这两段又都是树，就可以递归求解了。
当树的大小为0或1时，返回true。代码：
classSolution {
public:
bool VerifySquenceOfBST（vector<int> sequence） {
if（sequence.size（） == 0） {
return false;
}
returnVerify（sequence）;
} bool Verify（vector<int> sequence） {
intsize = sequence.size（）;
if（size <= 1） {
return true;
} //开始切割数列
vector<int> smaller; //第一段，比root小
vector<int> larger; //第二段，比root大
//根的值
introot = sequence[size - 1];
//判断此时是否还在第一段，若已经在第二段，但又回到了第一段
//则返回false
bool isOne = false;
//如果第一个数小于root，则表明有第一段，isOne为true
if（sequence[0] < root） {
isOne = true;
}
for（inti = 0; i < size - 1; i++） {
//比根小
if（sequence[i] < root） {
if（isOne == false） {
returnfalse;
}
smaller.push_back（sequence[i]）;
}
//比根大
else{
if（isOne）
isOne = false;
larger.push_back（sequence[i]）;
}
} returnVerify（smaller） && Verify（larger）;
}
};总结：
应该多弄点测试用例，自己测试完后，再提交二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-09/123319.htm