1. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解题思路：
- 递归法解决，上 n 级台阶的解法，等于 （n - 1）+ （n - 2）
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n <= 3) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
};
但是这种解法时间复杂度过高，可以优化。使用循环，并存储中间变量的方法。
leetcode 提交
2. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
解题思路：
- n 对括号，意味着每个字符串的长度为2n
- 通过递归，每一位放入左括号，或者，放入右括号，生成分支的递归树。得到所有的字符串组合。
- 在添加组合时，增加条件限制，去掉不合法的字符串。条件为（1. 左括号数量不能大于n， 2. 右括号数量不能大于左括号）
3 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
解题思路：
- 中序遍历，判断是否递增，递增则是二插搜索树，否则不是。
4. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
解题思路：
- 通过对二叉树的前序遍历，每下一层，记录一下层数。最后比较左右递归的返回值，返回较大的层数。
5. *二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路：
