輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回 true，否則返回 false。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

參考以下這顆二叉搜索樹：

5

/ \

2 6

/ \

1 3

示例

• 輸入: [1,3,2,6,5]

• 輸出: true

提示

• 數(shù)組長度 <= 1000

方法：遞歸分治

后序遍歷：

后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后遍歷根結(jié)點。即：【遍歷左子樹|遍歷右子樹|訪問根結(jié)點】。

二叉搜索樹：

在二叉搜索樹中：

• 若任意結(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均不大于它的根結(jié)點的值。

• 若任意結(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均不小于它的根結(jié)點的值。

• 任意結(jié)點的左、右子樹也分別為二叉搜索樹。

代碼如下：

復雜度分析

• 時間復雜度：O(N的2次方)， 每次調(diào)用 compare(i,j) 減去一個根節(jié)點，因此遞歸占用 O(N) ；最差情況下（即當樹退化為鏈表），每輪遞歸都需遍歷樹所有節(jié)點，占用 O(N) 。

• 空間復雜度：O(N)，最差情況下（即當樹退化為鏈表），遞歸深度將達到 N 。

END

世上無難事，只要肯攀登，贈友人。

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。