669. 修剪二叉搜索树 二刷再看迭代法。 修剪二叉搜索树可以不用像删除二叉搜索树中的节点一样分五种情况是因为隐含的删区间有一边的树肯定不符合就不用考虑了不像删节点还要保留，所以可以简化，还是利用递归返回点跳过被删除点实现删除。 当前节点的值比区间左边界小，那左子树不用考虑，递归继续修剪右子树，并将右子树修剪后的头结点返回，跳过这一层；如果这一层在边界内，就把左/右子树的修剪结果连接到这一层根节点，完成构建；当前节点的值比区间右边界大，那右子树不用考虑，递归继续修剪左子树，并将左子树修剪后的头结点返回，跳过这一层。 //C++ class Solution { public: TreeNode...

235. 二叉搜索树的最近公共祖先  有序树，如果中间节点是 q 和 p 的公共祖先，那么中节点的数组一定是在 [p, q]区间的，搜索树的最底层两边的叶子节点肯定是把根节点包在中间的。 上向下去递归遍历，第一次遇到 cur节点是数值在[p, q]区间中，那么cur就是 p和q的最近公共祖先，为什么是最近的呢，因为再往下遍历就会错过p和q，不存在更近的公共祖先了。 如果遍历到的点大于p和q（不确定p和q谁大），那么向左搜索，小于p和q，向右搜索，留下来的就是[p,q]和[q,p]注意是左闭右闭包含p和q本身就是公共祖先的情况。  迭代法，注意return root的时候else一定不能少，上面...

530.二叉搜索树的最小绝对差 二叉搜索树的性质，中序是有序数组，所以最小绝对值差其实可以转化为相邻元素的差，不开辟数组记录的话，可以用双指针（cur和pre）记录中序遍历输出的上一个节点和这个节点并更新插值，有几个细节注意。  pre是全局变量，这样才能确保递归回退的时候pre没有被回溯，要不旧的节点就丢失了。 pre要判空，要不第一个节点没有pre会报空指针异常。  //C++ class Solution { public: int result = INT_MAX; TreeNode* pre; int getMinimumDifference(TreeNode* root) { do...

654.最大二叉树 构造二叉树都是前序遍历，套路就是返回条件是构造的依据数组没有元素或者只有一个元素（叶子节点），从构造数组中取一个元素（依据题意，比如最大值，后序最后一个）作为节点，并以此节点作为分割边界分割构造数组，并将这个节点的左右节点指向左右分割子区间的递归结果，先处理当前节点，再左右，前序在遍历时构造节点，在遍历完返回的时候进行节点的连接，中序后序做不到。 //C++ 没看题解一遍过，棒 class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return...

513.找树左下角的值 层序遍历模板题。 //C# public class Solution { public int FindBottomLeftValue(TreeNode root) { Queue<TreeNode> que = new Queue<TreeNode>(); int res = 0; que.Enqueue(root); while (que.Count != 0) { int size = que.Count; for (int i = 0; i < size; i++) { TreeNode cur = que.Dequeue(); ...

110.平衡二叉树 求深度适合用前序遍历，而求高度适合用后序遍历。 巧妙设计递归三部曲中返回值的意义，比如这题返回-1就是非平衡，返回height就是平衡且还能计算高度，一举两得，如果返回值设计成bool那实际上不好计算每一次递归左右节点的高度，还是要算高度，返回height和-1就包含了bool的意思。 //C++ class Solution { public: bool isBalanced(TreeNode* root) { int height = getHeight(root); return height == -1 ? false : true; } int getHeight...

104.二叉树的最大深度  高度是节点到叶子节点的距离，相当于树站在地面上，深度是当前节点到二叉树顶点的距离. 后序求高度，处理逻辑在最后，当节点都遍历完后，子节点可以把自己的高度返回给父节点。 前序求深度，处理逻辑在最前，遍历时就动态更新每一步的深度值(需要一个全局参数来记录深度值的最大值)。 这两题层序遍历做过了已经，这里用递归的方式，后序和前序。 有没有注意到，后序递归是int返回值类型，而前序是void类型深度由参数记录。  后序遍历求根节点的最大高度（二叉树的最大深度 ） 根节点的高度就是二叉树的最大深度。 //C++ class Solution { public: int max...

层序遍历 10 借助队列，从一层开始，遍历每一层的每个元素出队进结果，左右孩子都入队，遍历完队列里只剩下一层的节点，保存节点个数，再遍历这一层得到下一层，直到队列为空。 C++ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> que; if (root == nullptr) return result; que.push(root); while...

理论基础 二叉树种类  满二叉树：每一层都填满，只有度为0或者2的节点，共有2^k - 1个节点（从1开始算层）。 完全二叉树：除最底层可能没被填满，其余每层都是满的（节点数量为2^（k - 1）），且最底层节点靠左。 二叉搜索树：有序树，左小右大。   若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树   平衡二叉搜索树：AVL树，要么空，要么左右两个子树的高度差不超过1，且都是平衡二叉搜索树，AVL树是map,set,multimap,multiset的底层实现，插入和查询的时间...

239. 滑动窗口最大值 暴力O(k * n),用单调队列（不是优先级队列，优先级序列改变了窗口内元素顺序，没法弹出），保证序列内元素时单调递减（队头始终是最大的元素）且只维护可能是最大元素的窗口元素，这样窗口移动丢弃元素同时需要队列弹出的时候，肯定是队列的头，因为其他比头小的元素早已经被弹出去了（头肯定是先进的元素，弹也是先弹旧的），不用管。具体实现三个函数。  push，放入单调序列的时候判断，如果新加的元素比前面的元素大，则前面的元素pop_back直到队列为空或者队列元素比新加的元素大。 pop，窗口移动移除末端元素时如果元素时队列中的头则队列头弹出pop_front，否则队列不用进行...

20. 有效的括号 这题有这种匹配（局部对称）的特征，用堆栈先进先出的结构很方便，通过遍历左括号，将右括号压栈，再在遍历到右括号的时候匹配栈内元素完成，很有哈希表算A+B = target用 A= target - B的意思，具体要考虑以下三种失效的情况。  遍历到右括号的时候，如果和栈顶元素不匹配，代表括号种类不匹配。 遍历到右括号的时候，如果栈内是空的，代表右括号是多余的，或者说没有左括号跟右括号匹配。 遍历完字符串时，如果栈还不是空，代表左括号是多余的，因为没有对应的右括号将栈内元素弹出。  当遍历完字符串且栈为空，则代表匹配。 C++ class Solution { public: ...

理论基础 栈与队列的底层实现有多种，可插拔，不归属于容器，而应该叫容器适配器。 232.用栈实现队列 分两个栈分别入、出，入直接进栈就可以，出栈需要分两种情况，如果出栈里有元素，弹一个出来就可以，如果是空的，要把所有入栈的元素都放到出栈里，保证顺序不变。 C++ 注意pop是void类型不返回值，要先通过top获取值，再把元素弹出。 class MyQueue { public: stack<int> stIn; stack<int> stOut; MyQueue() { } void push(int x) { stIn.push(x); } int pop() { ...

●28. 实现 strStr() ●459.重复的子字符串 ●字符串总结 ●双指针回顾 实现strStr（）  KMP算法的核心是前缀表，实际KMP就是为了避免不匹配时重新匹配，使用的技术是最长公共前后缀，因为每次不匹配时，已经扫过了文本串和模式串的后缀，而如果能知道和模式串后缀相等的最长相等前缀是多少，就能保证文本串的后缀（xxxxxaaxxxxx）和模式串的前缀（aaxxxaa）相等，这样这部分相等的就不用匹配了直接从模式串前缀的后一个字符开始匹配,文本串的指针也不用移动。而最长公共前后缀的长度恰好就是从0开始，继续匹配的索引位置（0 + 公共前缀长度 = 公共前缀的下一位下标），这样也就...

数据结构 数组 数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。 如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下： //C++ // 初始化一个长度为 5 的数组 array int array[5] = {0}; //全部初始化为00 int array[] = {2, 3, 1, 0, 2}; // 元素赋值 array[0] = 2; array[1] = 3; array[2] = 1; array[3] = 0; array[4] = 2; //C# 和C+的初始化方式不一样，在堆上要new空间 int[] a = new int[...