2019-12-10 刷题-2（栈）

最近在学习栈，目前都在刷栈的题目。

• 题目序号：101-对称二叉树
  本题有递归和迭代两种做法，递归比较简单，判断两个子树是否对称，相当于判断左左-右右以及左右-右左是否对称。迭代的做法可以手动模仿递归的压栈和出栈过程，每次按顺序压入左左，右右，左右以及右左的指针；每次出栈两个指针，直到栈为空，或提前终止迭代。
  代码：

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // only root node
        if(!root)
            return true;   // 边界条件判断
        if(!(root -> left) && !(root -> right))
            return true;
        
        stack<TreeNode *> node_stack;
        node_stack.push(root->left);
        node_stack.push(root->right);
        bool is_sym = true;
        
        while(!node_stack.empty()){
            TreeNode *r = node_stack.top();
            node_stack.pop();
            TreeNode *l = node_stack.top();
            node_stack.pop();           
            if (!r && !l)
                continue;
            if ((!r && l) || (r && !l)){
                return false;
            }
            if (l->val != r->val){
                return false;
            }
            node_stack.push(l->left);
            node_stack.push(r->right);
            node_stack.push(l->right);
            node_stack.push(r->left);
        }
        return is_sym;
    }
};

需要注意的地方：
1）需要考虑到根节点为空的情况，否则会runtime error.
2）节点先入栈再判断是否为空，判断逻辑会简单一些。
3）stack.pop()是void函数，为删除顶端元素。top()返回顶端元素。

补充（2020-2-26）
又想了一种基于层次遍历的做法，采用队列来存放要比较的两个子树，感觉更直观一些：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q1, q2;
        TreeNode *l = root -> left, *r = root -> right;
        q1.push(l);
        q2.push(r);
        while(!q1.empty() || !q2.empty()){
            l = q1.front();
            q1.pop();
            r = q2.front();
            q2.pop();
            if((l && !r) || (!l && r)) return false;
            if(l && r){
                if(l -> val != r -> val) return false;
                q1.push(l -> left);
                q1.push(l -> right);
                q2.push(r -> right);
                q2.push(r -> left);
            }
        }
        return true;
    }
};

• 20-有效的括号
  本题是学习栈的经典案例，其特性为，序列长度不固定，问题具有自相似性。对于一个括号序列，如果消去相邻的匹配的一对括号，原序列是否匹配取决于剩下的序列是否匹配。如，()([{}])，如果消去｛｝,剩下的()([])是否匹配决定了原序列是否匹配。
  基本思路为：遇到左括号则入栈，遇到右括号就出栈，如果匹配不上则该括号序列无效。当栈空而字符序列没有扫描完，表明右括号失配；否则，左括号失配。
  代码：

class Solution {
public:
    bool isValid(string s) {
        int l = s.length();
        stack<char> token_stack;

        // empty string
        if (l == 0)
            return true;
        
        for (int i = 0; i < l; i++){
            char c = s[i];
            if((c == '(') || (c == '[') || (c == '{'))
                token_stack.push(c);
            else{ 
                // ), ], or }
                if (token_stack.empty())
                    return false;
                char t = token_stack.top();
                token_stack.pop();
                switch(c){
                    case ')':
                    if (t != '(')
                        return false;
                    break;
                    case ']':
                    if (t != '[')
                        return false;
                    break;
                    case '}':
                    if (t != '{')
                        return false;
                    break;
                    default:
                    break;
                }
            }
        }
        return token_stack.empty();
    }
};