劍指 Offer 33. 二叉搜索樹的后序遍歷序列

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

?

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

? ? ?5

? ? / \

? ?2? ?6

? / \

?1? ?3

示例 1：

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

輸出: false

示例 2：

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

輸出: true

class Solution:
? ?def verifyPostorder(self, postorder: List[int]) -> bool:
? ? ? ?def judgeCur(i,j):
? ? ? ? ? ?if i>=j:return True
? ? ? ? ? ?p=i
? ? ? ? ? ?while postorder[p]<postorder[j]: p+=1
? ? ? ? ? ?m=p
? ? ? ? ? ?while postorder[p]>postorder[j]: p+=1
? ? ? ? ? ?if p!=j:return False
? ? ? ? ? ?else:
? ? ? ? ? ? ? ?return judgeCur(i,m-1)and judgeCur(m,j-1)
? ? ? ?return judgeCur(0,len(postorder)-1)
# 因?yàn)槭桥判蚨鏄?，所以?lt;中<右
# 因此先找到最后的為根節(jié)點(diǎn)，從數(shù)組左側(cè)開(kāi)始遍歷找到大于根節(jié)點(diǎn)的點(diǎn)，從這個(gè)點(diǎn)開(kāi)始為右子樹，前面的是左子樹。
# 關(guān)鍵在于判斷右子樹中的值是否全部大于根節(jié)點(diǎn)