代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true
,否则返回 false
。假设输入的数组的任意两个数字都互不相同。
参考以下这棵二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
提示:
数组长度 <= 1000
二叉搜索树的后序遍历序列是 [左子树, 右子树, 根结点]
,且左子树结点值均小于根结点,右子树结点值均大于根结点,递归判断即可。
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def verify(p1, p2):
if p1 > p2:
return True
pos = p1
while pos < p2 and postorder[pos] < postorder[p2]:
pos += 1
p = pos
while pos < p2:
if postorder[pos] < postorder[p2]:
return False
pos += 1
return verify(p1, p - 1) and verify(p, p2 - 1)
if not postorder:
return True
return verify(0, len(postorder) - 1)
class Solution {
public boolean verifyPostorder(int[] postorder) {
int n;
if (postorder == null || (n = postorder.length) == 0) return true;
return verify(postorder, 0, n - 1);
}
private boolean verify(int[] postorder, int p1, int p2) {
if (p1 >= p2) return true;
int pos = p1;
while (pos < p2 && postorder[pos] < postorder[p2]) ++pos;
int p = pos;
while (pos < p2) {
if (postorder[pos] < postorder[p2]) return false;
++pos;
}
return verify(postorder, p1, p - 1) && verify(postorder, p, p2 - 1);
}
}
/**
* @param {number[]} postorder
* @return {boolean}
*/
var verifyPostorder = function (postorder) {
if (!postorder || postorder.length < 2) return true;
let mid = 0;
let root = postorder[postorder.length - 1];
for (let i = 0; i < postorder.length - 1 && postorder[i] < root; i++) {
mid++;
}
for (let i = mid + 1; i < postorder.length - 1; i++) {
if (postorder[i] < root) return false;
}
return (
verifyPostorder(postorder.slice(0, mid)) &&
verifyPostorder(postorder.slice(mid + 1, postorder.length - 1))
);
};
func verifyPostorder(postorder []int) bool {
if len(postorder) < 2 {
return true
}
return helper(postorder, 0, len(postorder)-1)
}
// 递归
func helper(postorder []int , left,right int) bool {
if left >= right {
return true
}
// 最后一位即根
rootValue := postorder[right]
// 从左开始往右遍历,直到大于根停止,小于部分是左子树
i := left
for i < right && postorder[i] < rootValue {
i++
}
// 剩下部分是右子树,检查是否都大于根值
for j := i; j < right; j++ {
if postorder[j] < rootValue {
return false
}
}
l := helper(postorder,left,i-1) // 检查左子树,左子树i要减一
r := helper(postorder,i,right-1)// 检查右子树,剔除最后一位是根
return l && r
}
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return verify(postorder, 0, postorder.size() - 1);
}
bool verify(vector<int>& postorder, int left, int right) {
if (left >= right) {
return true;
}
int root = postorder[right], i = left;
while (postorder[i] < root) {
++i;
}
int mid = i;
while (i < right) {
if (postorder[i] < root) {
return false;
}
++i;
}
return verify(postorder, left, mid - 1) && verify(postorder, mid, right - 1);
}
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。