输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
如下:
5 / \ 2 6 / \ 1 3
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; } }