110.平衡二叉树 题目描述：给定一颗二叉树，判断它是否是平衡二叉树。 递归法 后序遍历 本题适合采用后序遍历，先遍历完左右子树，从底部开始累加高度。 后序遍历 class Solution { public: int getHight(TreeNode *node) { // 终止条件 if (!…
226.翻转二叉树 初印象: 感觉层序遍历一遍再倒过来就好了... 思路 实际上只要遍历每个节点并反转其左右孩子就可以了，因此用其他遍历方法都能做，除了递归法的中序遍历做不了，因为递归法的中序遍历会将某些节点的左右孩子翻转两次（按照左中右的顺序的话，先判断左，翻转，在判断右，这样的话此时的右就是刚刚…
二叉树的种类 完全二叉树 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。 满二叉树 二叉搜索树 前面介绍的树，都没有数值的，…
前置知识 用到了stoi(),以及to_string()两个函数 头文件#include<cstring> stoi() 和 atoi() stoi 的参数是 const string* 类型 atoi 的参数是 const char* 类型 stoi() 会对转化后的数进行检查，判断是…
关于栈和队列 STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有： 元素访问 st.top() 返回栈顶 修改 st.push() 插入传入的参数到栈顶 st.pop() 弹出栈顶 容量 st.empty() 返回是否为空 st.size() 返回元素数量 STL 中的 st…
151.翻转字符串里的单词 这一题主要的难点其实在于移除多余的空格. 如果想要让空间复杂度位O(1),也就是不采用辅助空间的话,我们应该想到双指针法. 整体思路大概是,快指针定位到单词的位置,再将单词插入慢指针所指向的位置,除了慢指针指向开头时,每次将快指针的值(也就是单词)赋给慢指针时,要先加一个…
344.反转字符串 class Solution { public: void reverseString(vector<char> &s) { for (int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--) { …
前置知识 C++中map，有三种类型： 映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::map 红黑树 key有序 key不可重复 key不可修改 O(log n) O(log n) std::multimap 红黑树 key有序 key可重复 key不可修改…
前置知识 在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示： 集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::set 红黑树 有序 否 否 O(log n) O(log n) std::multiset 红黑树 有序 是 …
24.两两交换链表中的节点 第一次尝试 超时了,推测是循环的问题 仔细想想好像是更新指针的问题,这一版代码的逻辑是先将curNode指向后两位的结点,然后再把nextNode指向curNode,然后再将curNode更新为curNode->next也就是curNode的后两位,再把nextNo…