Leetcode(栈的题解)

Leetcode_20

括号匹配

#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isValid(string s)
{
    stack<char> stack;
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]=='('||s[i]=='{'||s[i]=='[')
            stack.push(s[i]);
        else{
            if(stack.size()==0)
                return false;
            char c = stack.top();
            stack.pop();

            char match;
            if(s[i]==')')
                match = '(';
            else if(s[i]=='}')
                match = '{';
            else{
                assert(s[i]==']');
                match = '[';
            }
            if(c!=match)
                return false;
        }
    }
    if(stack.size()!=0)
        return false;
    return true;
}

Leetcode_144

前序遍历

#include <iostream>
#include <stack>
#include <string>
using namespace std;


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
    
};
struct Command
{
    string s;
    TreeNode* node;
    Command(string s, TreeNode *node):s(s),node(node) {}
    
};


vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> res;
    if(root==NULL)
        return res;

    stack<Command> stack;
    stack.push(Command("go",root));
    while(!stack.empty())
    {
        Command command = stack.top();
        stack.pop();
        if(command.s == "print")
            res.push_back(command.node->val);
        else{
            assert(command.s == "go");
            if(command.node->right)
                stack.push(Command("go",command.node->right));
            if(command.node->left)
                stack.push(Command("go",command.node->left));
            stack.push(Command("print",command.node));

        }

    }
    return res;
}