1. 爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

解題思路：

1. 遞歸法解決，上 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);
};

但是這種解法時間復(fù)雜度過高，可以優(yōu)化。使用循環(huán)，并存儲中間變量的方法。
leetcode 提交

2. 括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且 有效的 括號組合。

解題思路：

1. n 對括號，意味著每個字符串的長度為2n
2. 通過遞歸，每一位放入左括號，或者，放入右括號，生成分支的遞歸樹。得到所有的字符串組合。
3. 在添加組合時，增加條件限制，去掉不合法的字符串。條件為（1. 左括號數(shù)量不能大于n， 2. 右括號數(shù)量不能大于左括號）

leetcode 提交

3 驗證二叉搜索樹

給你一個二叉樹的根節(jié)點(diǎn) root ，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節(jié)點(diǎn)的左子樹只包含 小于 當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含 大于 當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。

解題思路：

1. 中序遍歷，判斷是否遞增，遞增則是二插搜索樹，否則不是。

leetcode 提交

4. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

解題思路：

1. 通過對二叉樹的前序遍歷，每下一層，記錄一下層數(shù)。最后比較左右遞歸的返回值，返回較大的層數(shù)。

leetcode 提交

5. *二叉樹的最近公共祖先

給定一個二叉樹, 找到該樹中兩個指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節(jié)點(diǎn) p、q，最近公共祖先表示為一個節(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點(diǎn)也可以是它自己的祖先）?！?/p>

解題思路：

原題解

leetcode 提交