1.   二叉树：

     （1） 最大深度： 递归， 最大深度等于左子树最大深度和右子树最大深度之间的最大值 + 1。

     （2） 最小深度： 递归，当左右子树均不为空时，最小深度等于左子树和右子树的最小深度之间的最小值 +1， 当有一边子树为空时，最小深度等于左子树最小深度和右子树最小深度之间的最大值+1.       

     （3）Symmetric Tree:  判断树是否是镜像树：

            递归的判断两棵树是否镜像，条件： 根节点的值相同，A的左子树和B的右子树镜像，A的右子树和B的左子树镜像。

class Solution {public:    bool isSymmetric(TreeNode* root) {     if (root == NULL) return true;     return checkSymmetric(root->left, root->right);    }private: bool checkSymmetric(TreeNode* p1, TreeNode *p2) { if (p1 == NULL && p2 == NULL) return true; if (p1 == NULL || p2 == NULL) return false; if (p1->val == p2->val) { return checkSymmetric(p1->left, p2->right) && checkSymmetric(p1->right, p2->left); } return false; }

      （4） 从先序和中序数组构造二叉树：

             先序数组第一个元素为根， 找到中序数组中的根，分为左子树和右子树进行递归。            

/** * 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:    TreeNode* buildTree(vector
     
      & preorder, vector
      
       & inorder) {        int ps = 0;        int pe = preorder.size() - 1;        int is = 0; int ie = inorder.size() - 1; return construct(preorder, inorder, ps, pe, is, ie); } private: TreeNode* construct(vector
       
        & preorder, vector
        
          inorder, int ps, int pe, int is ,int ie){ if (ps > pe) { return nullptr; } TreeNode* root = new TreeNode(preorder[ps]); int pos; for (int i =is; i <=ie; i++) { if (inorder[i] == root->val){ pos = i; break; } } root->left = construct(preorder, inorder, ps + 1, ps + pos - is, is, pos - 1); root->right = construct(preorder, inorder, ps + pos -is + 1, pe, pos+1, ie); return root; } };
        
       
      
     

      （5）有序数组构造搜索二叉树

   BST的根是数组的中位数结点。先构建根结点，再递归构造左子树和右子树。 如果改成有序链表构造二叉树，每次找到中间的结点是O（N）的， 用快慢指针，一个走一步，一个走两步。       

class Solution {public:    TreeNode* sortedArrayToBST(vector
     
      & nums) {        int len = nums.size();        if (len == 0) return NULL;        return constructTree(nums, 0, len-1); } private: TreeNode* constructTree(const vector
      
        &nums, int s, int e) { if (s > e ) return NULL; int mid = (s + e) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = constructTree(nums, s, mid - 1); root->right = constructTree(nums, mid + 1, e); return root; } };
      
     

    升级后的有序链表， 用一个全局listnode指针， 有序链表是中序遍历二叉树的结果，进行中序二叉树建立。

class Solution {public:    TreeNode* sortedListToBST(ListNode* head) {        if (head == NULL) return NULL;        ListNode *p = head;        int n = 0; while(p->next !=NULL) { p = p->next; n++; } node = head; return constructMidTree(head, 0, n); } private: ListNode* node; TreeNode* constructMidTree(ListNode* head, int s, int e){ if (s > e ) return NULL; int mid = (s + e) / 2; TreeNode* left = constructMidTree(head, s, mid-1); TreeNode* root = new TreeNode(node->val); node = node->next; root->left = left; root->right = constructMidTree(head, mid+1, e); return root; } };

 

2.  堆栈

 (1) 解码字符串 

  举例：s = "3[a]2[bc]", return "aaabcbc"， s = "3[a2[c]]", return "accaccacc"， s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

     采用一个stack<vector<int>>  s1 维护出现的次数，采用一个stack<vector<string>>  s2维护当前层次解码后的string, 妻子一个[]代表一个层次。遇到的字符分为三种情况，数字则s1入栈（连续的数字字符是一个数字），[则新建层次入s2, 字符则append到栈顶str, ]则解码一次减少一个层次，s1.pop().  s2.pop(), 扩展后更新s2.top().

   

string decodeString(string s) {        int len = s.size();        if (len == 0) return s;        int i = 0;        stack
     
       helper_count;        stack
      
        helper_string; helper_string.push(""); while (i < len) { if (s[i] >= '1' && s[i] <= '9') { int count = 0; while(s[i] !='[') { count = 10 * count + int(s[i] - '0'); i++; } helper_count.push(count); helper_string.push(""); i++; } else if ((s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= 'A' && s[i] <= 'Z')) { string top = helper_string.top(); helper_string.pop(); helper_string.push(top + s[i]); i++; } else { int top_count = helper_count.top(); helper_count.pop(); string top_str = helper_string.top(); helper_string.pop(); string upt_str; for (int c=0; c
      
     

 

(2)  计算式的后序表达

           3

         /     \       

       +      *

     /    \

     2    1      

Example 1:

Input: ["2", "1", "+", "3", "*"]Output: 9Explanation: ((2 + 1) * 3) = 9

  用一个stack<int> 维护数字，遇见数字则进栈， 遇见符号则从栈顶出来两个元素，计算（top2 * top1），计算结果入栈。

  复习： C++ 函数： 字符串数字 转数字：   atoi(string.c_str())

//string转char*： string str=“world”；const char *p = str.c_str();//char* 转stringstring s;char *p = "hello";//直接赋值s = p;

 

   

public:    int evalRPN(vector
     
      & tokens) {       int len = tokens.size();       stack
      
        helper;       for (int i = 0; i < len; i++) {           if (!isSymbol(tokens[i])) { helper.push(atoi(tokens[i].c_str())); } else { int top1 = helper.top(); helper.pop(); int top2 = helper.top(); helper.pop(); int new_top = compute(top2, top1, tokens[i]); helper.push(new_top); } } return helper.top(); } private: int compute(int x, int y, string symbol) { if (symbol == "+") return x + y; else if (symbol == "-") return x - y; else if (symbol == "*") return x * y; else return x / y; } bool isSymbol(string a) { if (a == "+" || a == "-" || a== "*" || a == "/"){ return true; } return false; }
      
     

 

(3) 统计化学元素

Input: formula = "Mg(OH)2"Output: "H2MgO2"Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}. 用一个栈维护数字，一个栈维护 stack

class Solution {public:    string countOfAtoms(string formula) {        int len = formula.size();        stack

 

 

复习map:

map
     
       myMap;map
      
        :: iterator iter;string test// 查找key是否存在：iter =  a.find(test); if (iter == myMap.end());//新加key:     myMap[test] = 0;  //若不存在则自动初始化为0。    mapStudent.insert(pair
       
        ("r000", "student_zero")); //迭代器刪除 iter = mapStudent.find("r123"); mapStudent.erase(iter); //用關鍵字刪除 int n = mapStudent.erase("r123");//如果刪除了會返回1，否則返回0 //用迭代器範圍刪除 : 把整個map清空 mapStudent.erase(mapStudent.begin(), mapStudent.end()); //等同於mapStudent.clear()