33. 二叉搜索树的后序遍历序列【难】

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9833.%20%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97/README.md

面试题 33. 二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

     5/ \2   6/ \1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

解法

方法一：递归

后序遍历的最后一个元素为根节点，根据二叉搜索树的性质，根节点左边的元素都小于根节点，根节点右边的元素都大于根节点。因此，我们找到第一个大于根节点的位置 $i$ ，那么 $i$ 右边的元素都应该大于根节点，否则返回 false。然后递归判断左右子树。

时间复杂度 $O(n^2)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组长度。

Python3

【LeetCode力扣刷题 | 剑指Offer 33. 二叉搜索树的后序遍历序列（思路讲解及Python3代码实现）程序员面试手撕代码必刷题库】 https://www.bilibili.com/video/BV1FK4y1j73k/?share_source=copy_web&vd_source=ed4a51d52f6e5c9a2cb7def6fa64ad6a

class Solution:def verifyPostorder(self, postorder: List[int]) -> bool:def dfs(l, r):if l >= r:return Truev = postorder[r] #根节点值i = lwhile i < r and postorder[i] < v:i += 1 #左子树遍历，确保都比根节点小【退出时，i位置为第一个右子树元素的位置】  j=iif any(x < v for x in postorder[j:r]):return False #右子树遍历，并检验是否都比 都比根节点大return dfs(l, j - 1) and dfs(j, r - 1) #递归左右子树return dfs(0, len(postorder) - 1)

Java

class Solution {private int[] postorder;public boolean verifyPostorder(int[] postorder) {this.postorder = postorder;return dfs(0, postorder.length - 1);}private boolean dfs(int l, int r) {if (l >= r) {return true;}int v = postorder[r];int i = l;while (i < r && postorder[i] < v) {++i;}for (int j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);}
}

C++

class Solution {
public:bool verifyPostorder(vector<int>& postorder) {function<bool(int, int)> dfs = [&](int l, int r) -> bool {if (l >= r) {return true;}int v = postorder[r];int i = l;while (i < r && postorder[i] < v) {++i;}for (int j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);};return dfs(0, postorder.size() - 1);}
};

Go

func verifyPostorder(postorder []int) bool {var dfs func(l, r int) booldfs = func(l, r int) bool {if l >= r {return true}v := postorder[r]i := lfor i < r && postorder[i] < v {i++}for j := i; j < r; j++ {if postorder[j] < v {return false}}return dfs(l, i-1) && dfs(i, r-1)}return dfs(0, len(postorder)-1)
}

TypeScript

function verifyPostorder(postorder: number[]): boolean {const dfs = (l: number, r: number): boolean => {if (l >= r) {return true;}const v = postorder[r];let i = l;while (i < r && postorder[i] < v) {++i;}for (let j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);};return dfs(0, postorder.length - 1);
}

Rust

impl Solution {fn dfs(start: usize, end: usize, max_val: i32, postorder: &Vec<i32>) -> bool {if start >= end {return true;}let root_val = postorder[end - 1];for i in (start..end).rev() {let val = postorder[i];if val > max_val {return false;}if val < root_val {return (Self::dfs(start, i, root_val, postorder)&& Self::dfs(i + 1, end - 1, max_val, postorder));}}Self::dfs(start, end - 1, max_val, postorder)}pub fn verify_postorder(postorder: Vec<i32>) -> bool {Self::dfs(0, postorder.len(), i32::MAX, &postorder)}
}

JavaScript

/*** @param {number[]} postorder* @return {boolean}*/
var verifyPostorder = function (postorder) {const dfs = (l, r) => {if (l >= r) {return true;}const v = postorder[r];let i = l;while (i < r && postorder[i] < v) {++i;}for (let j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);};return dfs(0, postorder.length - 1);
};

C#

public class Solution {private int[] postorder;public bool VerifyPostorder(int[] postorder) {this.postorder = postorder;return dfs(0, postorder.Length - 1);}private bool dfs(int l, int r) {if (l >= r) {return true;}int v = postorder[r];int i = l;while (i < r && postorder[i] < v) {++i;}for (int j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);}
}

Swift

class Solution {private var postorder: [Int] = []func verifyPostorder(_ postorder: [Int]) -> Bool {self.postorder = postorderreturn dfs(0, postorder.count - 1)}private func dfs(_ l: Int, _ r: Int) -> Bool {if l >= r {return true}let rootValue = postorder[r]var i = lwhile i < r && postorder[i] < rootValue {i += 1}for j in i..<r {if postorder[j] < rootValue {return false}}return dfs(l, i - 1) && dfs(i, r - 1)}
}

方法二：单调栈【难】

后序遍历的顺序为“左、右、根”，如果我们从右往左遍历数组，那么顺序就变成“根、右、左”，根据二叉搜索树的性质，右子树所有节点值均大于根节点值。

因此，从右往左遍历数组，就是从根节点往右子树走，此时值逐渐变大，直到遇到一个递减的节点，此时的节点应该属于左子树根节点。我们找到该节点，那么此后其它节点【左子树】都应该小于该父节点，否则返回 false。然后继续遍历，直到遍历完整个数组。

此过程，我们借助栈来实现，具体步骤如下：

我们首先初始化一个无穷大的父节点值 $m x$ ，然后初始化一个空栈。

接下来，我们从右往左遍历数组，对于每个遍历到的元素 $x$ ：

-如果 $x$ 大于 $m x$ ，说明当前节点不满足二叉搜索树的性质【即左子树的节点 > 左子树根节点】，返回 false。
- 否则，如果当前栈不为空，且栈顶元素大于 $x$ 【根->右，维护递减栈】，说明当前节点为左子树节点，我们循环将栈顶元素出栈并赋值给 $m x$ ，直到栈为空或者栈顶元素小于等于 $x$ ，然后将 $x$ 入栈。

遍历结束后，返回 true。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组长度。

【单调栈【基础算法精讲 26】】 https://www.bilibili.com/video/BV1VN411J7S7/?share_source=copy_web&vd_source=ed4a51d52f6e5c9a2cb7def6fa64ad6a
【o(n)找下一个更大元素】

Python3

class Solution:def verifyPostorder(self, postorder: List[int]) -> bool:mx = infstk = []for x in postorder[::-1]:#2）遇到左子树的节点 > 左子树根节点mx【不满足递减栈条件退出时的元素】，返回 `false`if x > mx:return False#1）根->右：维护单调递减栈while stk and stk[-1] > x:mx = stk.pop()stk.append(x)return True

Java

class Solution {public boolean verifyPostorder(int[] postorder) {int mx = 1 << 30;Deque<Integer> stk = new ArrayDeque<>();for (int i = postorder.length - 1; i >= 0; --i) {int x = postorder[i];if (x > mx) {return false;}while (!stk.isEmpty() && stk.peek() > x) {mx = stk.pop();}stk.push(x);}return true;}
}

C++

class Solution {
public:bool verifyPostorder(vector<int>& postorder) {stack<int> stk;int mx = 1 << 30;reverse(postorder.begin(), postorder.end());for (int& x : postorder) {if (x > mx) {return false;}while (!stk.empty() && stk.top() > x) {mx = stk.top();stk.pop();}stk.push(x);}return true;}
};

Go

func verifyPostorder(postorder []int) bool {mx := 1 << 30stk := []int{}for i := len(postorder) - 1; i >= 0; i-- {x := postorder[i]if x > mx {return false}for len(stk) > 0 && stk[len(stk)-1] > x {mx = stk[len(stk)-1]stk = stk[:len(stk)-1]}stk = append(stk, x)}return true
}

TypeScript

function verifyPostorder(postorder: number[]): boolean {let mx = 1 << 30;const stk: number[] = [];for (let i = postorder.length - 1; i >= 0; --i) {const x = postorder[i];if (x > mx) {return false;}while (stk.length && stk[stk.length - 1] > x) {mx = stk.pop();}stk.push(x);}return true;
}

JavaScript

/*** @param {number[]} postorder* @return {boolean}*/
var verifyPostorder = function (postorder) {let mx = 1 << 30;const stk = [];for (let i = postorder.length - 1; i >= 0; --i) {const x = postorder[i];if (x > mx) {return false;}while (stk.length && stk[stk.length - 1] > x) {mx = stk.pop();}stk.push(x);}return true;
};