【面试题】剑指offer24--判断一个序列是否为二叉树的后序遍历

今天药忘吃喽~ 2022-06-13 07:28 123阅读 0赞

比如给一个序列，判断该序列是否为某二叉树的后序遍历

比如\{5,7,6,9,11,10,8\}是下面的二叉树的后序遍历结果

![Center][]

如果输入\{7,4,6,5\}就不是任意一颗二叉树的遍历结果

所谓后序遍历，先访问左子树，再访问右子树，最后访问根节点

代码的实现：

#include<iostream>
    using namespace std;
    bool IsBST(int arr[], int length)
    {
    	if (arr == NULL || length < 0)
    	{
    		return false;
    	}
    	int root = arr[length - 1];
    	int i = 0;
    	for (i = 0; i < length - 1; ++i)
    	{
    		if (arr[i]>root)
    		{
    			break;
    		}
    	}
    	int j = i;
    	for (j=i;j<length-1;++j)
    	{
    		if (arr[j] < root)
    		{
    			return false;
    		}
    	}
    
    	bool IsBst_left = true;
    	if (i>0)
    	{
    		IsBst_left = IsBST(arr, i);
    	}
    
    	bool IsBST_right = true;
    	if (j < length - 1)
    	{
    		IsBST_right = IsBST(arr + i, length - i - 1);
    	}
    	return(IsBst_left && IsBST_right);
    }
    
    int main()
    {
    	int arr[] = { 5, 7, 6, 9, 11, 10, 8 };
    	//int arr[] = { 7, 4, 6, 5 };
    	int ret = 0;
    	ret = IsBST(arr, sizeof(arr) / sizeof(arr[0]));
    	if (ret == 0)
    	{
    		cout << "该数组序列不是一颗二叉树！" << endl;
    	}
    	if (ret == 1)
    	{
    		cout << "该数组序列是一颗二叉树！" << endl;
    	}
    	system("pause");
    	return 0;
    }

运行的结果：

![Center 1][]![Center 2][]

[Center]: /images/20220613/46c48ae35c4a463c8d700c00cdf174ff.png
[Center 1]: https://img-blog.csdn.net/20170701104525570?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20220613/362d030617674624a253163e6988fd32.png