🌕🌗 剑指 Offer 33. 二叉搜索树的后序遍历序列

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 思路：
        // 结合 中序遍历数组有序
        // 可以根据 中序数组 & 后序数组 构造数
        // 而由于是二叉搜索树，因此找到大于根节点的区间，进行拆分即可，不同特意将 后序数组 进行排序生成实际的中序数组
        int len = postorder.length;
        return mySol(postorder, 0, len - 1);
    }

    private boolean mySol(int[] postorder, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return true;
        }
        int val = postorder[right]; // 根节点的值
        // 左半区间值肯定小于 val，右半区间全部大于 val
        // 找到这个下标
        int index = left;
        while(index < right) {
            if(postorder[index] < val) {
                index ++;
            } else {
                break;
            }
        }
        // [index] >= val
        // 判断 [index, right] 全部 > val
        int cut = index;
        while(index < right) {
            if(postorder[index] < val) {
                return false;
            } else {
                index ++;
            }
        }
        return mySol(postorder, left, cut - 1) && mySol(postorder, cut, right - 1);
    }
}

---

输出