二叉搜索树的后序遍历序列
程序员文章站
2022-05-06 23:37:41
...
题目描述:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
题目解析:
对于后序遍历的序列来说,最后一个值应该是根节点。二叉搜索树的左子树都比根节点小,右子树都比根节点大。因此,对于后序序列,倒着往前找,比最后一个节点大的是二叉树的右子树的节点,比最后一个节点小的是二叉树的左子树的节点。如果在本该是右子树的地方出现了比根节点小的值,那就返回false,同理,本该出现左子树的地方出现了比根节点大的值,那就返回false.
AC代码:
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(size == 0)
return false;
return judge(sequence,0,size-1);
}
bool judge(vector<int>& a,int left,int right)
{
if(left >= right)
return true;
int mid = right;
//最终的i为左子树和右子树的分界部分
while(mid > left && a[mid-1] > a[right])
--mid; //第一个出现的右子树节点
for(int i = mid-1; i >= left; --i)
{
//此时遍历的序列是左子树部分,因此应全小于根节点
if(a[i] > a[right])
return false;
}
return judge(a,left,mid-1) && judge(a,mid,right-1);
}
};
(*^▽^*)
上一篇: Java实现二叉搜索树