欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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);
	}
};

(*^▽^*)

相关标签: 二叉搜索树