[关闭]
@smilence 2016-10-08T08:00:56.000000Z 字数 8213 阅读 7477

Chapter 4 Trees and Graphs

"The Rules"

推荐教材： http://people.cs.vt.edu/shaffer/Book/

1.关于Tree 

  1. //Definition for binary tree
  2.   struct TreeNode {
  3.       int val;
  4.       TreeNode *left;
  5.       TreeNode *right;
  6.       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  7.  };

Keywords: Binary Search Tree, Balanced Tree, Full tree, Complete Tree
BST适用于快速检索（ )，通过in-order遍历可以ascending输出sorted data。
DFS Traversal: In-order traversal, pre-order and post-order.
注意尽量不要在DFS中调用有DFS操作的函数，可以通过统一两个函数的返回值的办法来合并。
对树的所有操作务必注意边界条件( root == NULL)

2.Trie: 又称prefix tree或字典树。N-aray tree, 方便提供string或string前缀的快速检索。 Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

  1. class TrieNode {
  2. private:
  3.     char mContent;
  4.     bool mMarker;
  5.     vector<TrieNode*> mChildren;
  7. public:
  8.     Node() { mContent = ' '; mMarker = false; }
  9.     ~Node() {}
  10.     friend class Trie;
  11. };
  13. class Trie {
  14. public:
  15.     Trie();
  16.     ~Trie();
  17.     void addWord(string s);
  18.     bool searchWord(string s);
  19.     void deleteWord(string s);
  20. private:
  21.     TrieNode* root;
  22. };

3.Heap与priority_queue
Heap首先是一个Binary complete tree，其次是它满足partial order；从具体实现上说通常用array来实现，节点的位置关系通过index体现。
值得注意的是，heap的插入操作逐层sift-up，耗时，与Binary Tree的插入相同。但Build heap通过sift-down所有非叶子节点实现，耗时，小于BST的。

priority_queue是STL中heap的类模板。常用函数：top(),pop(),push(const val_type&),empty()，类似<stack>。
在初始化priority_queue时，应尽量使用其constructor，而非循环插入元素。在constructor模板中，需要声明comparison class，注意默认的param1 < param2对应max heap。

  1. //example: min heap for nodes based on their values
  2. struct comp{
  3.     bool operator() ( Node * param1, Node *param2 ){
  4.         return param1->val > param2->val;
  5.     }
  6. };
  8. void buildHeap(){
  9.     vector<Node *> vn;
  10.     priority_queue<Node *, vector<Node *>,comp> heap( vn.begin(), vn.end() );
  11. }

对于user-define的类型，也可以重载<预算符，而不声明comparison class。

4.Graph implementations
每个vertical用一个int类型的ID来代表，实际的数据可以存储在<vector>中。
a. adjacency matrix，space cost: ，适合密集graph, 可以用int[N][N]二维数组实现;
b. adjacency list, space cost: , 适合稀疏graph, 可以用vector<list<int> >来实现,vector的size为。
注：对于undirected graph中的edge，可以视作双向edge；
而标记visit状态的变量，可以作为node本身的属性，或利用数组/hashtable来实现

5.Graph Traversal (DFS and BFS)

  1. void graphTraverse( Graph *G ){
  2.     //much depends on your implementation for the graph
  3.     int v;
  4.     for( v = 0; v != G->n(); v++)
  5.         G->setMark( v, UNVISITED );
  6.     for( v = 0; v != G->n(); v++)
  7.         if( G->getMark(v) == UNVISITED )
  8.             doTraverse(G,v);  // can be DFS or BFS here
  9. }
  1. //DFS
  2. void DFS( Graph *G, int v ){
  3.     preVisit( G, v );
  4.     G->setMark( v, VISITING ); //use "VISITNG" to tag the state between previsit and postvisit
  5.     for( int w = G->first(v); w != G->n(); w = G->next(v,w) )
  6.         if( G->getMark(v) == UNVISITED )
  7.             DFS( G, w);
  8.     postVisit( G,v );
  9.     G->setMark( v, VISITED );
  10. }
  1. //BFS
  2. void BFS( Graph *G, int start ){
  3.     int v,w;
  4.     queue<int> Q;
  5.     G->setMark( start, VISITING );
  6.     Q.push( start );
  7.     while(!Q.empty()){
  8.         v = Q.front();
  9.         Q.pop();
  10.         visit( G, v );
  11.         G->setMark( v ,VISITED);
  12.         for( w = G->first(v); w != G->n(); w = G->next( v, w) )
  13.             if( G->getMark(w) == UNVISITED ){
  14.                 //you can also choose to visit here so you visit "earlier"
  15.                 G->setMark(w) = VISITING;  //use "VISITING" to identify "candidates" for visits
  16.                 Q.push(w);
  17.             }
  18.     }
  19. }

6.单源最短路径问题
Dijkstra算法，贪心算法( 局部最优解决定全局最优解），可以利用数学归纳法证明其正确性。
基本思路是找到局部最优的前驱节点，并据此update该节点的后驱节点，直到所有节点得到update。 

  1. class DijkElem{
  2. public:
  3.     int vertex, distance;
  4.     DijkElem( int v = -1, int d = numeric_limit<int>::max() ){
  5.         vertex = v;
  6.         distance = d;
  7.     }
  8. }
  10. bool operator<(const DijkElem &param1, const DijkElem &param2){
  11.     return param1.distance> param2.distance; //considering we need a min heap here.
  12. }
  14. void Dijkstra( Graph *G, int *D, int s){
  15.     int i,v,w;
  16.     DijkElem temp;
  17.     priority_queue<DijkElem> minHeap;
  19.     //initialize distance array, every node considered to be infinitely far from source
  20.     D = new int[G->n()];
  21.     for( i = 0; i < G->n(); ++i){
  22.         D[i] = numeric_limit<int>::max();
  23.     }
  25.     //start from the source;
  26.     temp.vertex = s;
  27.     temp.distance = 0;
  28.     minHeap.push(temp);
  29.     D[s] = 0;
  31.     for( i = 0; i < G->n(); ++i ){
  32.          //find a vertex with minimum distance each time
  33.         do{
  34.             if( minHeap.empty() ) return;
  35.             temp = minHeap.top();
  36.             minHeap.pop();
  37.             v = temp.vertex;
  38.         }while( G->getMark(v) == VISITED );
  39.         G->setMark(v,VISITED);
  40.         if( D[v] == numeric_limit<int>::max() )
  41.             return;
  43.         //update its children
  44.         for( w = G->first(v); w != G->n(); w = G->next(v,w) ){
  45.             if( D[w] > D[v] + G->weight(v,w) ){
  46.                 D[w] = D[v] + G->weight(v,w);
  47.                 temp.distance = D[w];
  48.                 temp.vertex = w;
  49.                 minHeap.push(w);
  50.             }
  51.         }
  52. }

模式识别

1.subGraph 或 subTree 的局部最优解解问题
如果全局解可以分割成subTree或subGraph 互相独立的局部解（即局部最优解推出全局最优解），一般可以采用D&C策略，用DFS递归判断subtree或subgraph的解，结合当前节点返回局部解。另见Chapter 7 Backtracking问题的相关说明。

e.g.1 Check if a binary tree is balanced. ( CtCI: 4.1, Leetcode:Balanced Binary Tree ) 

  1. // How to improve over this? (call another recursion within recursion)
  2. bool isBalanced(TreeNode* root) {
  3.     if (root == NULL) {
  4.         return true;
  5.     }
  6.     if (abs(depth(root->left) - depth(root->right)) > 1)
  7.         return false;
  8.     return isBalanced(root->left) && isBalanced(root->right);
  9. }
  11. int depth(TreeNode* root) {
  12.     if (root == NULL) {
  13.         return 0;
  14.     }
  15.     return max(depth(root->left), depth(root->right)) + 1;
  16. }
  1. // Optimal solution with aggregating two recursions
  2. bool isBalanced(TreeNode* root) {
  3.     if (root == NULL) {
  4.         return true;
  5.     }
  7.     return depth(root) != -1;
  8. }
  10. int depth(TreeNode* root) {
  11.     if (root == NULL) {
  12.         return 0;
  13.     }
  14.     int leftDepth = depth(root->left);
  15.     if (leftDepth == -1) {
  16.         return -1;
  17.     }
  18.     int rightDepth = depth(root->right);
  19.     if (rightDepth == -1) {
  20.         return -1;
  21.     }
  22.     if (abs(leftDepth-rightDepth) > 1) {
  23.         return -1;
  24.     }
  26.     return max(leftDepth,rightDepth) + 1;
  27. }

e.g.2 Check if a binary tree is a BST. ( CtCI: 4.5, Leetcode:Validate Binary Search Tree)
e.g.3 Check if T2 is a subtree of T1. ( CtCI: 4.8 )
e.g.4 Check if a graph has a cycle.
e.g.5 Given a binary tree, find its minimum depth.( Leetcode:Minimum Depth of Binary Tree）

  1.     int minDepth(TreeNode *root) {
  3.        if(root == NULL) return 0;       
  4.        int left = 0, right = 0;
  6.        if(root->left) left = minDepth(root->left);   
  7.        if(root->right) right = minDepth(root->right);
  9.        if(!left) return 1 + right;
  10.        else if(!right) return 1 + left;
  11.        else return 1 + min(left,right);
  13.     }

2.Tree的path问题
一般来说，属于 问题。( 将在Recursion一章提到）
对于tree的单向path问题（每条path，每层只经过一个节点），则使用DFS来访问tree，可以利用一个vector<int> &path来记录路径（毕竟，对于backtracking来说，每次只需考虑一条path即可，无论这条path通往“胜利条件”与否 ），并在每次访问时判定是否满足“胜利条件”，返回bool值或在胜利情形下将当前的路径path记录下来。注意在postVisit节点时path.pop_back();

e.g.1 Given a binary tree, print all paths which sum to a give value.(CtCI: 4.9)
e.g.2 Given a binary tree, find all root-to-leaf paths which sum to a given value.(Leetcode: Path Sum II)
Solution: http://paste.ofcode.org/JvvHJVBCYtRRvLnKHw6puW

3.将Tree转换成其他Data Structure的问题
如果是分层转换，则使用BFS，用list<TreeNode *> parents与list<TreeNode *> children记录邻近的两层，代替<queue>。如果不是，则类似 1类问题，采用D&C策略，将root->left与root->right两个subtree分别转换成目标数据结构，返回“适当的变量”，再处理root节点。如果是将其他数据结构转换为tree，则类似：将两部分递归转换成subtree，然后处理当前节点。

e.g.1 Given a binary tree, creates linked lists of all the nodes at each depth( CtCI 4.4 )
e.g.2 Given a binary tree, flatten it to a linked list in-place. （Leetcode: Flatten Binary Tree to Linked List)
e.g.3 Convert a binary tree into a doubly linked list in place. (CtCI 17.13)
e.g.4 Convert a sorted array( increasing order ) to a balanced BST. ( CtCI 4.3, Leetcode: Convert Sorted Array to Binary Search Tree )

4.寻找特定节点
给定节点，寻找与之有相对关系的特定节点的问题。首先应该以当前节点为root 考虑当前子树（左支、右支）；如果不在当前子树，则向上考虑：a. 有parent节点，则沿parent节点逐层往上查找 b.无parent节点，则由root节点DFS查找给定节点；特别地，对于BST，则只需由root节点单向向下查找。

e.g. 1 Find the in-order successor of a given node, with parent links. (CtCI: 4.6)
e.g. 2 Find the in-order successor of a given node in BST, without parent links. 

  1. TreeNode *inorderSucc( TreeNode *given, TreeNode *root ){
  3.     if(given == NULL )
  4.         return NULL;
  6.     if(given->right){
  7.         given = given->right;
  8.         while(given->left)
  9.             given = given->right;
  10.         return given;
  11.     }
  13.     TreeNode* succ = NULL;
  15.     while(root && root != given){
  16.         if( given->val <= root->val ){
  17.             succ = root;
  18.             root = root->left;
  19.         }else{
  20.             root = root->right;
  21.         }
  22.     }
  24.     return succ;
  25. }

e.g.3 Find the first common ancestor of two nodes in a binary tree, with .( CtCI 4.7 )
e.g.4 Find the immediate right neighbor of the given node, with parent links given, but without root node.( Ebay interview question) 

  1. TreeNode *findByLvl( TreeNode *root, int lvl ){
  3.     if( root == NULL )
  4.         return NULL;
  6.     if( lvl == 0 )
  7.         return root;
  9.     TreeNode *left = findByLvl(root->left,lvl+1);
  10.     if( left ) return left;
  11.     else    return findByLvl(root->right,lvl+1);
  12. }       
  14. TreeNode* rNeighbor( TreeNode *given ){
  16.     TreeNode *parent = given->parent;
  17.     int level = -1;
  19.     while(parent){
  21.         while( parent && parent->left != given ){
  22.             given = parent;
  23.             parent = given->parent;
  24.             level--;
  25.         }
  27.         if( parent == NULL )
  28.             return NULL;
  30.         TreeNode *local = findByLvl( parent->right, level + 1);
  32.         if(local)
  33.             return local;
  34.         else{
  35.             given = parent;
  36.             parent = given->parent;
  37.             level--;
  38.         }
  39.     }
  41.     return NULL;        
  42. }

5.Graph的访问
绝大多数关于Graph的interview question, 都基于简单的DFS或BFS。通常来说，与路径或最短路径相关的问题，用BFS解决；全局的判定问题，可以用DFS。
寻找最短路径的问题，原则上使用Dijkstra算法，特别地，对于unweighted graph，由于从source开始访问的最小深度就等效于到该节点的最短路径，因此Dijkstra算法就退化成BFS，min heap退化成<queue>，并且可以用distance[i] = -1来表示该节点unvisited。
如果需要记录路径，对于DFS可以用vector<int> &path单向记录，对于BFS可以记录每一个节点的前驱节点，即int prev[G->n()]，最后用递归来整理vector<int> path。

e.g.1 Given a directed graph,find out whether there is a route between two nodes ( CtCI: 4.2 )
e.g.2 Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary ( CtCI: 18.10, Leetcode: Word Ladder II )
Solution: http://paste.ofcode.org/Vwd3BDguN3fdKQkJDRjeyN

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注