树
树的题目，基本是二叉树，不过面试时如果没有说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
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
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){