二叉搜索樹的後序遍歷序列

前言

本來是九度oj是一道三星的acm題目，但是同樣在《劍指offer》這本書上有所提及，正好我看的時候發現了一處錯誤，這裡糾正一下

概念

二叉搜索樹（binary search tree），或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不為空，則左子樹上所有結點的值均小於它的根結點的值;若它的右子樹不為空，則右子樹上所有結點的值均大於它的根節點的值。它的左、右子樹也分別為二叉排序樹。

注意：

根據概念我們可以明確的知道，二叉搜索樹的左、右子樹均可為空。構建二叉搜索樹或者是遍歷可以參考這篇文章：

http://www.linuxidc.com/Linux/2013-05/85117.htm

題目

題目描述：
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
輸入：
每個測試案例包括2行：
第一行為1個整數n(1<=n<=10000)，表示數組的長度。
第二行包含n個整數，表示這個數組，數組中的數的范圍是[0,100000000]。
輸出：
對應每個測試案例，如果輸入數組是某二叉搜索樹的後序遍歷的結果輸出Yes，否則輸出No。
樣例輸入：
7
5 7 6 9 11 10 8
4
7 4 6 5
樣例輸出：
Yes
No

思路分析

在後序遍歷得到的序列中，最後一個數字是樹的根節點的值。數組中前面的數字可以分為兩部分：

• （1）第一部分是左子樹結點的值，它們都比根結點的值小
• （2）第二部分是右子樹結點的值，它們都比根結點的值大

根據上述性質，所以我們可以寫一個遞歸函數：

1. 遞歸的終止條件是當前樹的結點總數為0
2. 判斷是否是二叉排序樹的方法：首先，找到第一個大於根結點的結點位置，將數組分為兩部分，判斷右子樹中的全部結點是否均大於根結點的值

指出《劍指offer》中的錯誤： 當長度為0時應該返回true，原因是左、右子樹可空

AC代碼

#include <stdio.h>
#include <stdlib.h>
 
#define false 0
#define true 1
 
int judge_bst(int *arr, int len);
 
int main()
{
    int i, n, flag, arr[100001];
 
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i ++)
            scanf("%d", &arr[i]);
       
        flag = judge_bst(arr, n);
        (flag == 1) ? printf("Yes\n") : printf("No\n");
    }
 
    return 0;
}
 
int judge_bst(int *arr, int len)
{
    int i, j, root;
   
    // 遞歸終止條件
    if (len <= 0)
        return true;
 
    root = *(arr + len - 1);
 
    // 區分左子樹
    for (i = 0; i < len - 1; i ++) {
        if (*(arr + i) > root)
            break;
    }
 
    // 查找右子樹是否符合要求
    for (j = i; j < len - 1; j ++) {
        if (*(arr + j) < root)
            return false;
    }
 
    // 遞歸的判斷左右子樹是否符合要求
    int left, right;
    left = true;
    left = judge_bst(arr, i);
 
    right = true;
    right = judge_bst(arr + i, len - 1 - i);
 
    return (right && left);
}
 
/**************************************************************
    Problem: 1367
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:1228 kb
****************************************************************/