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

微软等数据结构与算法面试100题 第九题

第九题
判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
         8
      /  \
     6    10
    / \  / \
   5  7 9  11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

分析:
本题目是考察后序遍历二叉搜索树的性质,即右子树大于根节点大于左子树,因此可以递归使用这个性质作为判定。

首选整个树的根节点在序列末尾,然后确定去左子树和右子树是否满足上面的性质,在这里需要指出的是,可以不用判定右子树是否大于根节点,因为右子树再进行拆分判定的时候又可以分为判定左右子树,因此可以不用判定右子树而只判定左子树。
递归程序的出口即为判定的序列长度为2和3时,即只有左子树和根节点、左子树右子树和根节点两种情况,针对这两种情况分别写出判定方法和返回值。

代码:
[cpp] 
#include<iostream> 
 
using namespace std; 
 
  
bool CheckSeqBSTree(int * sequence, int startIndex ,int length) 

    if(NULL==sequence||length==0) 
        return false; 
    //找到左右子树的分割符 
    int i = startIndex; 
    int leftLength = 0; 
    int rightLength = 0; 
 
    for(; i < startIndex + length -1 ; i++, leftLength++) 
    { 
        if(sequence[i]>sequence[startIndex+length-1]) 
            break;       
    } 
     
    rightLength = length - leftLength - 1; 
 
    //说明:其实右子树可以不用判断的 因为每次把右子树都会再继续拆分成左右子树,只判断左子树具有完备性 
    bool BSTree = false; 
    //check后面的点是否大于 
     
    //for(; i < length -1 ; i++) 
    //{ 
    //  if(sequence[i]<sequence[length-1]) 
    //      BSTree = false; 
 
    //} 
     
    //递归程序出口 
    if(length==2) 
    { 
        if(sequence[startIndex]<sequence[startIndex+1]) 
            BSTree = true; 
    } 
    else if (length==3) 
    { 
        if(sequence[startIndex]<sequence[startIndex+2]&&sequence[startIndex+1]>sequence[startIndex+2]) 
            BSTree = true; 
    } 
    else 
    { 
        BSTree= CheckSeqBSTree(sequence,startIndex,leftLength) && CheckSeqBSTree(sequence,i,rightLength); 
    } 
     
 
    return BSTree; 

int main() 

 
    int a[] = {5, 7, 6,9, 11, 10, 8}; 
 
 
    cout<<CheckSeqBSTree(a,0,7); 
 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,