后序遍历二叉搜索树的序列判别

[编程题]后序遍历二叉搜索树的序列判别

热度指数：55 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

如下:

示例1

输入

[1,6,3,2,5]

输出

false

示例2

输入

[1,3,2,6,5]

输出

true

算法知识视频讲解

南屏机修组扛把子

妙，妙啊

发表于 2022-12-15 15:32:25 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Solution {
    // 后序遍历二叉搜索树判断-单调栈
    public boolean verifyPostorder (int[] postorder) {
        ArrayDeque<Integer> s = new ArrayDeque<>(); // 单调栈-需要之前的root
        int root = Integer.MAX_VALUE; // 一开始最大
        for (int i = postorder.length-1; i >= 0; i--) {
            if (postorder[i] > root) return false; // 比根大直接返回
            while (!s.isEmpty() && s.peek() > postorder[i]) {
                root = s.pop(); // 左值比root小改为左值
            }
            s.push(postorder[i]); // 右值比root大继续存
        }
        return true;
    }
}

发表于 2022-07-17 12:32:20 回复(0)