樹
樹的題目，基本是二叉樹，不過面試時如果沒有說binary，千萬不要先入為主，可能是多叉的（這也是個陷阱，等你思路都差不多時，面試官說：我都沒有說是二叉樹，然後你就黑了），不要自己給自己增加條件了。樹的題目主要有以下幾種：
一. 樹的三種遍歷。前序、中序、後序，如果直接考遍歷，就肯定是讓你寫非遞歸代碼的（遞歸版太弱智了），具體寫法，要不你記下來，要不參考“遞歸”部分的，怎麼遞歸轉非遞歸，另一個就是給個中序+前序（後序），讓你還原二叉樹，中序必須給，不然還原不了（解不唯一），一般遞歸解決；
二. BST（Binary Search Tree）。這個考法多一點，怎麼判斷是不是BST（或者平衡樹，或者完全樹），有序數組（有序鏈表）轉換成BST，在BST中找某個upper_bound的最大值（這個可以給root讓你找符合要求的節點，可以給一個等於upper_bound的節點，有parent指針，讓你找），然後還有其他其他
三. LCA（Least Common Ancestor，最近公共祖先）。超高頻題，主要考法是給兩個指針和樹的root，找LCA，如果節點有parent節點（這時候就不給root了），就相當於鏈表找第一個交點了，如果沒有parent就要麻煩一點；
四. 序列化與發序列化。這個考法比較簡單，就是寫一個序列化和發序列化的方法，有思考過的話直接就可以秒了，一樣的問題還有字符串數組的序列化。一般思路是加一個記錄分段信息的head或者加一個不會出現的字符作為一種分割。有時候會說任何字符都可能出現，這時候可以用轉義字符（想想C的字符串怎麼記錄\的吧）。
一．樹的遍歷。
直接考的話就是非遞歸的程序了，前序、中序比較好改寫，後序要麻煩一點，自己手工模擬棧研究下吧（參考我前面寫的遞歸轉迭代：面試總結之-遞歸算法分析）。給一個參考的code：
[cpp] struct Node{
TreeNode* t_node_;
bool sign; //記錄這個節點是不是訪問過了
Node(TreeNode* n){
t_node_ = n;
sign = false;
}
};
void PostOrder(TreeNode* root){
stack<Node> stk;
stk.push(Node(root,false));
while(!stk.empty()){
Node tmp = stk.top();
stk.top().sign = true;//從棧頂拿出來過一次，置為true
if(tmp.sign){
visit(tmp.t_node_);
stk.pop();
}else{
if(tmp.t_node_->right)
stk.push(tmp.t_node_->right);
if(tmp.t_node_->left)
stk.push(tmp.t_node_->left);
}
}
}
struct Node{
TreeNode* t_node_;
bool sign; //記錄這個節點是不是訪問過了
Node(TreeNode* n){
t_node_ = n;
sign = false;
}
};
void PostOrder(TreeNode* root){
stack<Node> stk;
stk.push(Node(root,false));
while(!stk.empty()){
Node tmp = stk.top();
stk.top().sign = true;//從棧頂拿出來過一次，置為true
if(tmp.sign){
visit(tmp.t_node_);
stk.pop();
}else{
if(tmp.t_node_->right)
stk.push(tmp.t_node_->right);
if(tmp.t_node_->left)
stk.push(tmp.t_node_->left);
}
}
}
其實struct裡面不記錄bool sign也行，在迭代時記錄上一次訪問的節點pre，如果pre==top.right或者top.right==NULL，就可以pop，這樣的話更省空間，不過這種做法不是處處適用，為了統一各種轉非遞歸的方法，我把信息都記錄到了Node裡面。其他遍歷可以自己寫一下。給中序遍歷+前（後）序遍歷還原二叉樹的題，在leetcode上有，一會把樹的代碼總結到一起。
二． BST（Binary Search Tree）。
前面提到的BST題目感覺寫起來都不算特別麻煩，大概說說其中一個高頻題：有序鏈表轉BST。一種做法是，遍歷鏈表，找到中點，中點作為root，再遞歸處理左右兩邊，這樣的話時空復雜度是O(nlogn)+O(1)，另一種方法是把鏈表所有指針存到vector中，這就轉化成了有序數組轉BST的問題，有了隨機下標訪問，就可以O(1)時間找到中點了，然後還是遞歸處理左右部分，時空復雜度O(n)+O(n)。這個代碼也放到代碼總結那一塊。
三．LCA（Least Common Ancestor，最近公共祖先）。
LCA貌似一般不會考那種預處理之後O(1)找LCA的方法，一般都是在線算法。給parent的很好搞，就是兩個鏈表找第一個相交的節點：要不遍歷一遍第一個鏈表，做hash，遍歷第二個鏈表的時候找到第一個在hash裡面的節點即為所求,O(h)+O(h)（h是樹的高度）；要不分別跑一遍兩個鏈表，假設分別有a，b（a>=b）個節點，那麼第一個鏈表先走a-b步，然後兩個鏈表一起走，每走一步判斷一次兩個節點是不是相同，返回第一個相同的，時空復雜度O(h)+O(1)，不過這個要分別走兩次鏈表。
不給parent的一般接口就是這樣TreeNode* LCA(TreeNode* root,TreeNode* p1,TreeNode* p2)。我一般的做法是在函數參數中弄一個整形參數，記錄以當前節點為根的子樹，包含p1,p2中的幾個。
Code：
[cpp] node* lca(node* root,node* p1,node* p2,int& num){
if(!root) { num = 0;return NULL;}
int leftnum =0,rightnum=0;
node* left = lca(root->left,p1,p2,leftnum); //左子樹找到直接返回
if(leftnum==2) return left;
node* right = lca(root->right,p1,p2,rightnum);//右子樹
if(rightnum==2) return right;
num = left+right;
if(p1==root) num++;
if(p2==root) num++;
if(num==2) return root; //找不到計算當前樹
return NULL; //都找不到返回NULL
}
node* lca(node* root,node* p1,node* p2,int& num){
if(!root) { num = 0;return NULL;}
int leftnum =0,rightnum=0;
node* left = lca(root->left,p1,p2,leftnum); //左子樹找到直接返回
if(leftnum==2) return left;
node* right = lca(root->right,p1,p2,rightnum);//右子樹
if(rightnum==2) return right;
num = left+right;
if(p1==root) num++;
if(p2==root) num++;
if(num==2) return root; //找不到計算當前樹
return NULL; //都找不到返回NULL
}
這部分都是一個題目一個解，沒總結出啥共性。
四．序列化與發序列化。
一個序列化的方法可以參考這個：http://blog.csdn.net/ssjhust123/article/details/7777665這種方法用一個不出現的字符作為終結符。如果題目說節點的value是一個可以允許任意字符的string的話，就用轉義字符解決吧。既然樹的序列化，那就避免不了樹節點的序列化了，如果樹節點的value是一個字符串數組，那麼，樹序列化的子問題就是這個字符串序列化的問題，沒別的~繼續用轉義字符解決吧。
最後一點要注意的，遞歸處理樹的時候，遞歸返回條件經常用到兩種:
[cpp] (1) if(!node) return;
(2) if(!node->left&&!node->right) return;
(1) if(!node) return;
(2) if(!node->left&&!node->right) return;
這兩種差別在於，第一種會在非葉子節點return回去（比如當前面的節點有右兒子沒有左兒子時，在進入左兒子後會有一個return，當然，要是遞歸前你有加一個if(root->left) Recursive()的話，是不會進入這個NULL節點的，不過我為了簡潔，一般不加）；第二種只有到了葉子節點才會返回。這兩個還是有區別的，差別就在於題目的解是不是必須在葉子節點出現，比如讓你找root到葉子節點的最短距離，一般就用第二個判斷條件比較合適，具體自己寫寫體會一下吧。
另外，如果對於要不要往某個兒子遞歸進行了判斷（if(root->left)），那麼你就不知道有沒有進入這個兒子節點，就不知道你的這個兒子節點需要更新的變量有沒有被更新，這時候這些變量的初始化就要額外小心。
這段話的意思還是給個例子來解釋下吧，比如如下代碼：
[cpp] int Max(TreeNode* root){
int left,right;
if(!root->left && !root->right)
return root->val;
if(root->left) left = Max(root->left);
if(root->right) right = Max(root->right);
return max(root->val,max(left,right));
}
int Max(TreeNode* root){
int left,right;
if(!root->left && !root->right)
return root->val;
if(root->left) left = Max(root->left);
if(root->right) right = Max(root->right);
return max(root->val,max(left,right));
}這種代碼時有問題的，因為left和right的值有可能沒有初始化，你不確定程序有沒有遞歸處理左、右部分。它用了(2)這種遞歸返回條件，要是想用這個條件的話，就需要對left，right進行初始化，比如：
[cpp] left = right = MIN_INT；
left = right = MIN_INT；如果用(1)這個返回條件的話，可以寫成：
[cpp] int Max(TreeNode* root){
if(!root) return MIN_INT;
return max(root->val,max(Max(root->left),Max(root->right)));
}
int Max(TreeNode* root){
if(!root) return MIN_INT;
return max(root->val,max(Max(root->left),Max(root->right)));
}
相對來說，用（1）就要簡潔一點。這裡不一定要用（2）的原因就是上面說的：解不是必須在葉子節點出現。因為if(!root->left && !root->right)這種條件就是為了判斷root是不是一個葉子，而例子中的Max函數根本不需要一定要求這個值所在的位置是一個葉子。
簡單說，能用（1）的盡量用（1）（比如上面的LCA，也可以改成用（2）的），但是對於前面一定要在葉子節點結束的就沒辦法了，這時候，進行遞歸的時候將需要判斷if(root->child)，如果這個函數有變量返回，比如一個depth，那就要注意這個變量的值，因為這個遞歸你不一定會進入的，depth如果沒有初始化過的話，又沒有進入遞歸，那麼depth可能是個不可預測的值，後面需要用到depth的話注意判斷，也可以先給depth一個值，比如depth返回的是最大深度，可以把depth初始化為INT_MIN 。
對於遞歸處理樹時，首先想好使用（1）還是（2）作為終止條件（主要判斷是不是只能在葉子終止），如果用了（2）記得在遞歸時判斷兒子是不是為NULL，然後變量需要初始化。
