【算法】剑指 Offer 33. 二叉搜索树的后序遍历序列

    科技2023-10-02  72

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

    class Solution { public: bool verifyPostorder(vector<int>& postorder) { int n = postorder.size(); if(n < 1) return 1; int m = INT_MAX; stack<int> root; root.push(INT_MIN); for(int i = n - 1; i >= 0; --i) { if(postorder[i] > m) return 0; while(postorder[i] < root.top()) { m = root.top(); root.pop(); } root.push(postorder[i]); } return 1; } };

    这个代码巨简洁,说实话并没有怎么看懂

    Processed: 0.008, SQL: 8