面试总结之-树

树

树的题目，基本是二叉树，不过面试时如果没有说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到叶子节点的最短距离，一般就用第二个判断条件比较合适，具体自己写写体会

补充：软件开发 , C++ ,