最近做的六道題稍微復盤一下

二叉樹的序列化和反序列化

一道非常經(jīng)典的題目。我首先的思路是將任意一棵樹當做滿二叉樹處理，這樣的話需要先求出二叉樹深度，通過二叉樹深度初始化一個很大的數(shù)組（可能樹的結(jié)點不多，所以數(shù)組會有很多空值）。這種方式不好的地方就是時間和空間復雜度都比較高。

后來想了想，使用先序遍歷的方式將所有的結(jié)點記錄在字符串中，然后再返回，就和Leetcode官方二叉樹表示相同。

對于反序列化的話，首先需要做字符串的初始化處理。因為是先序遍歷，先序還原即可。將字符串分解成字符串數(shù)組，這里需要注意數(shù)字的表示范圍（上面也要注意，對于空節(jié)點使用null表示），以免Integer.parse出問題。

具體的代碼如下：

最大的BST子樹

這道題使用兩次dfs遍歷，第一次找出最大的BST。第二次對于這棵BST進行計數(shù)。

判斷一棵樹是否是BST：

1. 如果左子樹和右子樹中有一顆不是BST 當前也不是

2. 如果左子樹和右子樹都是，并且當前的節(jié)點的值大于左邊的最大值，小于右邊的最小值，則當前也是。

這樣的方法比較慢。

根據(jù)左程云講的方法，對于當前的二叉樹，需要返回這樣的幾個信息：

1. 當前樹的最小值和最大值

2. 當前樹（子樹）中的BST的根節(jié)點

3. 當前樹的大小

我將這些量統(tǒng)一在一個Info類中。如果dfs返回為空，可能是因為當前樹沒有左子樹或者右子樹，也可能是因為從左子樹或右子樹中找不到BST。針對以上的可能性，我可以分類，然后給出結(jié)果。以上兩種思路的代碼如下：

二叉樹的最近公共祖先

規(guī)定dfs的返回值如果當左右節(jié)點不為空時，表示當前節(jié)點的左右子樹包含p、q，如果左子樹不為空，右子樹為空，返回左子樹的返回值。這是因為結(jié)果會線組合好，返回的值就是根節(jié)點；左子樹返回值為空，右子樹返回值為空同理； 代碼如下：

水壺問題

如果仔細分析示例1的過程，可以想出兩種辦法，第一種是使用遞歸。將所有的操作嘗試，但是這種方式不好，因為很難確定什么時候結(jié)束遞歸；第二種方式我發(fā)現(xiàn)可以將操作的過程整理為一個不定方程的形式：

ax + by = z，我參考了題解才知道這個方程的解確定可以通過貝祖定理。

貝祖定理：當z能整除ab的最大公因數(shù)時，方程有確定解。那么 代碼如下：

其他兩個題不難，都是常規(guī)問題，這里就是pass了~