题目:

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

思路:

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

在后序遍历得到的序列中， 最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：
第一部分是左子树结点的值，它们都比根结点的值小
第二部分是右子树结点的值，它们都比根结点的值大。

代码:

#import <Foundation/Foundation.h>



/**
 判断 numArray 是否 是 后序 遍历 结果

 @param numArray 数字 数组
 @param startIndex 开始 索引
 @param endIndex 结束 索引
 @return 返回 是否 一致
 */
BOOL postorderTraversal (int *numArray, int startIndex, int endIndex) {
    
    if (numArray == NULL) {
        return NO;
    }
    
    if (startIndex >= endIndex) {
        return YES;
    }
    
    int tmpLeft = startIndex;
    
    while (tmpLeft < (endIndex - 1) && numArray[tmpLeft] < numArray[endIndex]) {
        tmpLeft ++;
    }
    
    int tmpRight = tmpLeft;
    
    while (tmpRight < (endIndex - 1) && numArray[tmpRight] > numArray[endIndex]) {
        tmpRight ++;
    }
    
    if (tmpRight != endIndex - 1) {
        return NO;
    }
    
    return postorderTraversal(numArray, startIndex, tmpLeft - 1) && postorderTraversal(numArray, tmpRight, endIndex - 1);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int data[]  = {4, 8, 6, 12, 16, 14, 10};
        NSLog(@"%d", postorderTraversal(data, 0, 7));
        
    }
    return 0;
}