只标注困难和简单的题目，中等题不标注
树的遍历
中，后，前序遍历题，n叉树，二叉树的遍历 层次遍历（简单) (主要复习一下非递归的解法）

94 中序遍历√
144 前序遍历√
145 后序遍历√
589 n叉树前序遍历√
590 n叉树后序遍历√
429 n叉树层序遍历√
102 二叉树的层次遍历√
[236. 二叉树的最近公共祖先
[257. 二叉树的所有路径 √（递归、栈均可）

二叉搜索树

[98. 验证二叉搜索树
[230. 二叉搜索树中第K小的元素
[LeetCode] 272. Closest Binary Search Tree Value II 最近的二分搜索树的值之二
[LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
[LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
[783. 二叉搜索树结点最小距离
[173 二叉搜索树迭代器 √
[LeetCode] 251. Flatten 2D Vector 压平二维向量
[LeetCode] 281. Zigzag Iterator 之字形迭代器
[LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
[501. 二叉搜索树中的众数（Morris）√
[98 验证二叉搜索树 （中序遍历是否符合大小规则）√
[99. 恢复二叉搜索树（Morris）√（困难）
[671. 二叉树中第二小的节点（简单）
[1305. 两棵二叉搜索树中的所有元素
面试题34. 二叉树中和为某一值的路径
[leetcode] 325. Maximum Size Subarray Sum Equals k

学习到的新知识
Morris中序遍历

Morris中序遍历

首先明确：在二叉搜索树中，如果一个结点有前驱结点，那么前驱结点的右指针只有两种情况

是空的

是这个结点本身（即前驱是它的父结点）

所以我们可以把前驱结点的右指针这一特性利用起来，从而降低空间复杂度
Morris遍历算法的步骤如下：
检查当前结点的左孩子:
如果当前结点的左孩子为空，说明要不没有前驱，要不前驱是它的父结点，所以进行检查，然后进入右孩子。

如果当前结点的左孩子不为空，说明左子树里肯定有它的前驱，那就找到这个前驱

如果前驱结点的右孩子是空，说明还没检查过左子树，那么把前驱结点的右孩子指向当前结点，然后进入当前结点的左孩子。

如果当前结点的前驱结点其右孩子指向了它本身，说明左子树已被检查过，就直接进行检查，然后把前驱结点的右孩子设置为空，恢复原树，再进入右孩子。

在遍历过程中，每个节点最多会被访问两次，一次是从父节点到当前节点，第二次是从前缀节点的右孩子指针返回当前节点，所以Morris遍历算法的复杂度是O(n)。在遍历过程中，没有申请新内存，因此算法的空间复杂度是O(1).
平衡二叉树
DFS 深度优先搜索

[46. 全排列（DFS） √
[47. 全排列 II（不必求出所有的全排列 DFS+ 剪枝） √
[113. 路径总和 II (DFS + 状态重置）√
[112. 路径总和 （DFS）√
[437. 路径总和 III（两次递归 或者 前缀和）√
路径和 IV

[491. 递增子序列（深度优先搜索+剪枝判重 unordered_map） √
[31. 下一个排列
[60. 第k个排列
[77. 组合
[529. 扫雷游戏（DFS BFS均可）
[756. 金字塔转换矩阵
[LeetCode] 267. Palindrome Permutation II 回文全排列之二
[996. 正方形数组的数目（困难）

C++中find()函数用法
//find() 返回值是目标元素的下标，找不到时返回值为迭代器结尾
find(track.begin(), track.end(), nums[i]) == track.end()

C++ std::unordered_map 用法
在容器中搜索键值等于 k 的元素，如果找到，则返回一个指向该元素的迭代器，否则返回一个指向unordered_map :: end的迭代器。
动态规划

[300. 最长上升子序列 √（动态规划 N^2  √  优化：NlogN）
[646. 最长数对链
递增的三元子序列
俄罗斯套娃信封问题 （困难 ）
最长数对链
最长递增子序列的个数
两个字符串的最小ASCII删除和

贪心算法

[646. 最长数对链
[435. 无重复区间(medium)
[991. 坏了的计算器
[300. 最长上升子序列

窗口

[1297. 子串的最大出现次数

其他：

[284. 顶端迭代器 √
[640. 求解方程（分别处理左右表达式获取常数与变量系数）
[728. 自除数
面试题 16.07. 最大数值（位运算，(sum+abs)/2）√

目录
该题目出自：剑指 Offer 55 - II. 平衡二叉树
题目描述：
知识点
解题思路
代码块

该题目出自：剑指 Offer 55 - II. 平衡二叉树
题目描述：
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
示例 :

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

知识点
1.什么是平衡二叉树？

   如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
2.怎么计算一棵树的深度？

   【运用递归方法的思想】

   特殊情况：如果节点为空时，则深度为0；

    树的深度的求解方法：max(左子树深度，右子树深度)+1

代码实现：
private int depth(TreeNode root){
	if(root==null) return 0;
    return Math.max(depth(root.left),depth(root.right)) +1;
}

解题思路
明确了以上两个知识点，应用递归法解决【强烈推荐递归法的思路，可以大大减少代码量】

解决这道题的思路如下：

0.特殊情况：如果节点为空时，则返回true;

1.对根节点进行判断，分别求出它的左右子树的深度，且二者相差不超过1，这为判断该树是否平衡的条件一；

2.根节点的左右子树也得为平衡树，即它们分别的左右子树深度差不超过1，若其中一个不为平衡树，则整棵树都不是平衡的，明显得用到递归的方法去遍历判断。
代码块
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){return true;}//特殊情况
        //递归法解答，三个条件缺一不可进行判断。
        return Math.abs(depth(root.left)-depth(root.right))<=1
               &&isBalanced(root.left)&&isBalanced(root.right);
    }
    private int depth(TreeNode root){
        //计算树的深度的方法
        if(root==null){return 0;}//特殊情况
        return Math.max(depth(root.left),depth(root.right)) +1;}
}

平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
题目解析
题目要求判断一棵树是否是平衡二叉树，首先我们需要了解平衡二叉树的数据结构如下，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。所以我们可以使用递归方式去得到左右子树的高度如下
代码
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
        if(root == null){
            return true;
        }
        return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && IsBalanced_Solution(root.left) && 
            IsBalanced_Solution(root.right);
    }
    //得到树的深度
    private int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(getDepth(root.left),getDepth(root.right));
    }
}

平衡二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int MAX(int a,int b)
{
    return a > b ? a : b;
}

//求高度
int getHeight(struct TreeNode *root){
    if(root == NULL){
        return 0;
    }

    int left =getHeight(root->left);
    int right =getHeight(root->right);

    return MAX(left,right)+1;
}
bool isBalanced(struct TreeNode* root){
    if(root == NULL){
        return true;
    }
    //左子树是不是平衡二叉树
        bool is_left_balance =isBalanced(root->left);
        if(is_left_balance == false){
            return false;
        }
	//右子树是不是平衡二叉树
        bool is_right_balance =isBalanced(root->right);
        if(is_right_balance == false){
            return false;
        }
        int left_height = getHeight(root->left);
        int right_height = getHeight(root->right);
        int diff =left_height-right_height;
	//左右子树高度差要小于1	
        if(diff >= -1 && diff <=1){
            return true;
        }else{
            return false;
        }
}

根据二叉树创建字符串

class Solution {
public:
    string tree2str(TreeNode* t) {
        if(t==nullptr)
            return "";
        stringstream ss;
        function<void(TreeNode*)> helper = [&ss, &helper](TreeNode* t){
            ss<<t->val;
            if(t->left==nullptr){
                if(t->right!=nullptr){
                    ss<<"()(";
                    helper(t->right);
                    ss<<')';
                }
            }
            else if(t->right==nullptr){
                ss<<'(';
                helper(t->left);
                ss<<')';
            }
            else{
                ss<<'(';
                helper(t->left);
                ss<<")(";
                helper(t->right);
                ss<<')';
            }
        };
        helper(t);
        string s;
        ss>>s;
        return s;
    }
};