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

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

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/