class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
}
};
剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
提示：
数组长度 <= 1000原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-14 11:07:34
func verifyPostorder(postorder []int) bool {
var dfs func(i,j int) bool
dfs = func(i,j int) bool {
if i >=j {
return true
}
p:=i
for postorder[p]< postorder[j] {
p++
}
m := p
for postorder[p] > postorder[j] {
p++
}
return p == j && dfs(i,m-1) && dfs(m,j-1)
}
return dfs(0, len(postorder)-1)
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-14 11:07:13
func verifyPostorder(postorder []int) bool {
if len(postorder) < 2 {
return true
}
index := len(postorder) - 1// 区分左右子树：左子树上的值全都比根节点小，右子树上的值全都比根节点大
rootValue := postorder[index]// 用来记录根节点的值
for k, v := range postorder {
// 当出现第一个大于根节点的值时，这个值往后全是右子树
if index == len(postorder)-1 && v > rootValue {
index = k
}
// 在右子树中出现小于根节点的值时，则该树不是二叉搜索树
if index != len(postorder)-1 && rootValue > v {
return false
}
}
return verifyPostorder(postorder[:index]) && verifyPostorder(postorder[index:len(postorder)-1])
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-11-14 11:06:28
class Solution:
def verifyPostorder(self, postorder: [int]) -> bool:
stack, root = [], float("+inf")
for i in range(len(postorder) - 1, -1, -1):
if postorder[i] > root: return False
while(stack and postorder[i] < stack[-1]):
root = stack.pop()
stack.append(postorder[i])
return True
python3 解法, 执行用时: 36 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-14 11:06:03
class Solution:
def verifyPostorder(self, postorder: [int]) -> bool:
def recur(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
return p == j and recur(i, m - 1) and recur(m, j - 1)
return recur(0, len(postorder) - 1)