算法整理-二叉树和堆栈

客官°小女子只卖身不卖艺 2021-12-15 14:51 155阅读 0赞

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<int>& preorder, vector<int>& 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<int>& preorder, vector<int> 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<int>& nums) {
            int len = nums.size();
            if (len == 0) return NULL;
            return constructTree(nums, 0, len-1); } private: TreeNode* constructTree(const vector<int> &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<int> helper_count;
            stack<string> 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<top_count; c++) { upt_str += top_str; } upt_str = helper_string.top() + upt_str; helper_string.pop(); helper_string.push(upt_str); i++; } } return helper_string.top(); }

(2)  计算式的后序表达

/     \\

+      \*

/    \\

2    1

Example 1:

Input: ["2", "1", "+", "3", "*"]
    Output: 9
    Explanation: ((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* 转string
    string s;
    char *p = "hello";//直接赋值
    s = p;

*   *

public:
        int evalRPN(vector<string>& tokens) {
           int len = tokens.size();
           stack<int> 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<map<string,int>>, 遍历时分为一下几种情况，字符，则判断后续有没有数字，更新栈顶元素，左括号则新建层次，右括号则减去一个层次。

class Solution {
    public:
        string countOfAtoms(string formula) {
            int len = formula.size();
            stack<map<string, int>> helper;
            map<string, int> init; helper.push(init); int i = 0; while (i < len) { if (formula[i] >= 'A' && formula[i] <= 'Z'){ string cur = ""; cur = formula[i++]; cout << cur; while(i < len && formula[i] >= 'a'&& formula[i] <= 'z'){ cur += formula[i++]; } int count = 1; if (i < len && isnumber(formula[i])) { count = 0; while(i< len && isnumber(formula[i])){ count = count * 10 + (formula[i] - '0'); i++; } } // update map top element  updateTop(helper, make_pair(cur, count)); } else if (formula[i] == '(') { map<string, int> temp; helper.push(temp); i++; } else if (formula[i] == ')') { i++; int count = 1; if (i < len && isnumber(formula[i])) { count = 0; while(i < len && isnumber(formula[i])){ count = count * 10 + (formula[i] - '0'); i++; } } mergeTop(helper, count); // merge top1 * count + top2 to the new top  } } map<string, int>::iterator iter; map<string, int> final = helper.top(); string result=""; for (iter = final.begin(); iter != final.end(); iter++){ result += iter->first; if (iter->second > 1) result += to_string(iter->second); } return result; } private: bool isnumber(char s) { if (s >= '0' && s <= '9') return true; return false; } void updateTop(stack<map<string, int>> &helper, const pair<string, int>p) { map<string, int> &top_map = helper.top(); //map<string, int>::iterator iter = top_map.find(p.first); top_map[p.first] += p.second; return; } void mergeTop(stack<map<string, int>>& helper, const int count) { map<string, int> top1_map = helper.top(); helper.pop(); map<string, int> &top2_map = helper.top(); map<string, int>::iterator iter; for (iter = top1_map.begin(); iter != top1_map.end(); iter++) { //map<string, int>::iterator iter_find = top2_map.find(iter->first); top2_map[iter->first] += iter->second * count; } return; } };

复习map:

map<string, int> myMap;
    map<string, int> :: iterator iter;
    string test
    
    // 查找key是否存在：iter =  a.find(test); if (iter == myMap.end());
    
    //新加key: 
    
        myMap[test] = 0;  //若不存在则自动初始化为0。
        mapStudent.insert(pair<string, string>("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()

转载于:https://www.cnblogs.com/cookcoder-mr/p/11080068.html