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

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

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷結果。

思路：最後一個數字是樹的根節點，數組可以分成2部分：

- 第二部分：右子樹，他們都比根節點大

參考代碼：

#include <stdio.h>int bst(int* seq,int len){ if(seq == NULL || len < 0) return 0; int root = seq[len - 1]; int i = 0; for(;i <len -1;++i) { if(seq[i] > root) break; } int j = i; for(;j < len -1;++j) { if(seq[j] < root) return 0; } int left = 1; if(i > 0) left = bst(seq,i); int right = 1; if(i < len -1) right = bst(seq + i,len -i - 1); return (left && right);}int main(){ int arr[] = {5,7,6,9,11,10,8}; int res = bst(arr,sizeof(arr)/sizeof(int)); printf("%d
",res); return 0;}

推薦閱讀：