LeetCode 面試題33. 二叉搜索樹的后序遍歷序列【劍指Offer】【Medium】【Python】【遞歸】
問題
輸入一個(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
提示：
數(shù)組長度 <= 1000
思路
遞歸
根據(jù)性質(zhì)：
1. 后序遍歷：左右根
2. 二叉搜索樹：左子樹任意節(jié)點(diǎn)的值 < 根節(jié)點(diǎn)的值媒区，右子樹任意節(jié)點(diǎn)的值 > 根節(jié)點(diǎn)的值
劃分左右子樹锚烦，分別判斷子樹是否滿足二叉搜索樹性質(zhì)扩然。
其他看代碼注釋艘儒。
時(shí)間復(fù)雜度: O(n^2)，n 為節(jié)點(diǎn)個(gè)數(shù)夫偶。
空間復(fù)雜度: O(n)界睁，n 為節(jié)點(diǎn)個(gè)數(shù)。
Python3代碼
from typing import List
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(i, j):
# 根節(jié)點(diǎn)小于等于1個(gè)
if i >= j:
return True
l = i
# 左子樹
while postorder[l] < postorder[j]:
l += 1
# 找到第一個(gè)大于根節(jié)點(diǎn)的節(jié)點(diǎn)兵拢，記為 m
m = l
# 右子樹
while postorder[l] > postorder[j]:
l += 1
# postorder[j]是根
return l == j and recur(i, m - 1) and recur(m, j - 1)
return recur(0, len(postorder) - 1)
