day16二叉树（三） && day11栈与队列（Ⅱ）【补】

day16
代码随想录
2023.12.14
今天三道题感觉本身没难度，都用层次遍历的思想能解决。。。二叉树的最大深度和最小深度昨天做过了，就不再记录了。

1. 222完全二叉树的节点个数
这道题有很多解法，任何遍历的方法都可以解决，只不过是访问值时，有一个变量表示个数++；深度遍历的三种方法，又细分为递归和迭代。包括昨天的层序遍历方法等等，各种解法五花八门，我这里用的层序遍历方法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int result = 0;
        queue<TreeNode*> que;
        if(root!=NULL)
            que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i=0;i<size;i++){
                TreeNode*node = que.front();
                que.pop();
                result++;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result;
    }
};

day11
之后补一下第11天的博客，因为今天内容比较少，就两篇博客写成一篇。

1. 22有效括号
这道题本身没难度，逻辑也很简单，但在一行代码一直报地址错误，：如果s[i]是右括号，且栈顶是相匹配的左括号，则说明匹配正确，栈顶元素弹出。这一行代码的的if判断一直报错。开始很不理解。‘）{’，在这种情况下，感觉没错啊，开始是右括号‘）’，但栈顶不是相应的左括号啊，就if判断错呗，后来才发现，此时，栈根本就是空，所以访问栈顶元素这个操作就不对！，因此报地址错误。后来给每个if语句加了个栈不为空，即可通过！

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        if (s.size() % 2 != 0) return false;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || s[i]=='{' || s[i]=='[')
                st.push(s[i]);
            else if(!st.empty() && s[i]==')' && st.top()=='('){
                st.pop();
            }
            else if(!st.empty() && s[i]==']' && st.top()=='['){
                st.pop();
            }
            else if(!st.empty() && s[i]=='}' && st.top()=='{'){
                st.pop();
            }
            else   
                st.push(s[i]);
        }
        if(st.empty())
            return true;
        return false;
    }
};

2. 1047删除字符串中的所有重复相邻项
这道题，有点消消乐的味道了，emm。其实如果不懂栈，感觉看这道题还是有点难度的。跟上一道题很相似，一个是判断括号匹配，这个是判断是否相同，这么一说，相信大家都懂了。按，上道题逻辑，最后得到一个栈，里面包含最终删除相邻重复的结果。所以将栈内元素弹出，都赋值给一个新string，但要注意，此时string顺序是相反的，所以需要reverse一下。
其实在这道题开始写的一直结果有问题，最终result都为空。。最后原因是，我在将栈元素给result时，用的result[i]…这种形式，但string类型好像不允许这种赋值形式，只能通过该形式访问元素，赋值需要通过“+”，之后修改后，通过！

class Solution {
public:
    string removeDuplicates(string s) {
        string result="";
        stack<char> st;
        if(!s.empty())
            st.push(s[0]);
        for(int i=1;i<s.size();i++){
            if(!st.empty() && st.top()==s[i]){
                st.pop();
            }
            else
                st.push(s[i]);
        }
        int size = st.size();
        
        for(int i=0;i<size;i++){
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
    
};

3. 150逆波兰表示求值
这道题是典型的栈应用问题，用一个栈记录计算数，然后遍历vector，遇到操作符，就弹出两个计算数，再将结果压入栈，最后栈里的唯一元素就是结果。
再说一说写代码遇到的问题，首先，给的vector是string类型，对于C++来说，string和char一个是双引号，另一个是单引号。开始一直写的单引号，最后才发现该问题，修改了。另一个问题，也就是遇到数字，但数字在vector中是string类型的，怎么转化为int呢？查了很多资料，有很多内置函数，但在leetcode都用不了，最后看了官方答案关于这一步的操作，也是用了指定函数。。。这种东西，知道就行了，不算技术难点，最终通过！

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/"){
                int number1 = st.top();
                st.pop();
                int number2 = st.top();
                st.pop();
                if(tokens[i]=="+")
                    st.push(number2+number1);
                else if(tokens[i]=="-")
                    st.push(number2-number1);
                else if(tokens[i]=="*")
                    st.push(number2*number1);
                else if(tokens[i]=="/")
                    st.push(number2 / number1);
            }
            else
                st.push(std::atoi(tokens[i].c_str()));  //官方答案中的转换方法
        }
        return st.top();
    }
};