[Lc]面试题31栈的压入、弹出序列

题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

这个就用一个栈来模拟压入，出栈就可以了。每存一个数要检查当前的popped数组的首位

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int j = 0;//定义指针j指向popped的下标，从0开始
        for(int i=0; i<pushed.size(); ++i){
            s.push(pushed[i]);
            //若弹出的值等于栈顶，且s不为空（为空使用pop()会报错），j没超出范围
            while(!s.empty() && j<popped.size() && s.top()==popped[j]){
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
};