leetcode部分题目合集

旧城等待， 2022-05-22 13:37 233阅读 0赞

**1、题目描述**  
Given a binary tree，find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node。  
解析：  
通过BFS层序遍历树，找到第一个叶子节点，即为最短的深度。

class Solution {
    public:
        typedef TreeNode* tree;
        int run(TreeNode *root) {
          //采用广度优先搜索，或者层序遍历，找到的第一个叶节点的深度即是最浅。
          if(root == NULL)//防御性编程 
              return 0;
          queue<tree> qu;
          tree last,now;//last记录当前村层最后一个节点，now表示当前正在处理的节点
          int level,size;
          last = now = root;//初始化
          level = 1;//层数为1
          qu.push(root);
          while(qu.size()){
       //BFS依次遍历树，直到找到第一个叶子节点
            now = qu.front();
            qu.pop();
            size = qu.size();
            if(now->left)
                qu.push(now->left);
            if(now->right)
                qu.push(now->right);
    
            if(qu.size()-size == 0)//前面两个左右节点都为空，那么找到了第一个叶子节点。直接结束并返回
                break;
            if(last == now){
       //当前节点=当层最后节点，那么level可以加1。
              level++;
              if(qu.size())
                  last = qu.back();//取出下一层的最后一个节点。
            }
          }
          return level;
        }
    };

**2、题目描述**  
Evaluate the value of an arithmetic expression in Reverse Polish Notation.  
Valid operators are+,-,\*,/. Each operand may be an integer or another expression.  
Some examples:

\[“2”, “1”, “+”, “3”, “*“\] -> ((2 + 1)*  3) -> 9  
\[“4”, “13”, “5”, “/”, “+”\] -> (4 + (13 / 5)) -> 6

意思是给定一个逆波兰表达式，求该表达式的值  
思路：由于逆波兰表达式本身不需要括号来限制哪个运算该先进行，因此可以直接利用栈来模拟计算：遇到操作数直接压栈，**碰到操作符直接取栈顶的2个操作数进行计算（注意第一次取出来的是右操作数(也就是代码中的num2)**），然后再把计算结果压栈，如此循环下去。最后栈中剩下的唯一一个元素便是整个表达式的值。

#include<stack>
    #include<string>
    using namespace std;
    class Solution {
    public:
        int evalRPN(vector<string> &tokens) {
            stack<int> s;//临时栈
            for(int i = 0 ; i < tokens.size() ; i++){
                string Temp = tokens[i];
                if(Temp == "+" || Temp == "-" || Temp == "*" || Temp == "/"){
                    if(s.size() < 2)//是运算符，则栈参数必须大于2
                        return 0;
                    int num2 = s.top();//取出第二个操作
                    s.pop();
                    int num1 = s.top();
                    s.pop();
                    if(Temp == "+")
                        s.push(num1+num2);
                    else if(Temp == "-")
                        s.push(num1-num2);
                    else if(Temp == "*")
                        s.push(num1*num2);
                    else
                         s.push(num1 / num2);
                }else//如果是字符串数字，则直接转换成数字压栈即可
                    s.push(atoi( Temp.c_str() ) );
            }
            return s.top();//栈中最后一个元素就是最后计算的结果
        }
    };