当前位置:编程学习 > C/C++ >>

二叉搜索树的后序遍历序列(判断后序遍历序列是否合法)

(1)题目描述
题目描述:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
输入:
每个测试案例包括2行:
第一行为1个整数n(1<=n<=10000),表示数组的长度。
第二行包含n个整数,表示这个数组,数组中的数的范围是[0,100000000]。
输出:
对应每个测试案例,如果输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No
(2)程序实现
       二叉搜索树的性质是:元素的左子树上的元素全部小于该元素,右子树上的元素全部大于该元素。后序遍历根节点总是在最后,所以根据后序遍历顺序可以得到根元素,并且得到根元素的左子树和右子树。假设树的后序遍历顺序为:3,7,4,6,5;可以判断出:5是根节点,3为根节点的左子树,7,4,6是根节点的右子树,但是右子树需要保证所有节点大于根节点,所以这个顺序不是二叉搜索树的后序遍历顺序。
       解题思路:在标识出左右子树时,遍历右子树,发现右子树中的元素小于其父节点,则顺序为错误的。(PS:这种解法还需要优化,目前想到的办法是存储两个变量,标识子树中元素的最大值和最小值,还需要优化)
 
[cpp]  
#include <iostream>  
   
using namespace std;  
   
bool IsValid(int *data, int n, int left, int right)  
{  
     if(left>=right)  
         return true;  
     int mid = 0;  
     int root = data[right];  
      //标识左子树,右子树的分割位置  
     for(mid = left; mid<right,data[mid]<root; ++mid)  
         ;  
      //判断子树是否合法  
     for(int i=mid; i<right; ++i)  
     {  
         if(data[i]<root)  
             return false;  
     }  
     if(!IsValid(data, n, left, mid-1))  
         return false;  
     if(!IsValid(data, n, mid+1, right))  
         return false;  
     return true;  
}  
   
int main()  
{  
    int n;  
    while(cin>>n)  
    {  
        int *data = new int[n];  
        for(int i=0; i<n; ++i)  
            cin>>data[i];  
        if(!IsValid(data, n, 0, n-1))  
            cout<<"No"<<endl;  
        else  
            cout<<"Yes"<<endl;  
                delete[] data;  
    }  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,