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

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-25 21:36:58
    编辑于：2022-02-25 22:57:33
    浏览量：648

概述

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

递归法

根据最后一个值即根节点的值，我们可以将前面的值划分为左右两部分。

class Solution {
public:
    vector<int> postorder;
    bool verifyPostorder(vector<int>& postorder) {
        this->postorder = postorder;
        return helper(0, postorder.size() - 1);
    }

    bool helper(int l, int r) {
        if (l >= r) return true;
        int rootVal = postorder[r];
        int i;
        for (i = l; i < r; i ++) {
            if (postorder[i] > rootVal) break;
        }
        for (int k = i; k < r; k ++) {
            if (postorder[k] < rootVal) return false;  // 开始时把 k 写成了 i，淦，看来半天，用了 CLion 我才发现
        }
        auto res = helper(l, i - 1) && helper(i, r - 1);
        return res;
    }
};

Links: sword-offer-33