212 Word Search II

来源：Leetcode

原帖：https://leetcode.com/problems/word-search-ii/

题目：
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
 [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
 ]
Return ["eat","oath"].

代码：

 struct TrieNode {  
   bool isWord;  
   string word;  
   unordered_map<char, TrieNode*> next;  
   TrieNode(bool w = false) : isWord(w) {}  
 };  
   
 class Solution {  
 public:  
   void insert(TrieNode*& root, string s) {  
     if (!root) root = new TrieNode();  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
     }  
     cur->isWord = true;  
     cur->word = s;  
   }  
     
   vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
   void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j,   
       TrieNode* root, vector<string>& res) {  
     int M = board.size(), N = board[0].size();  
     char c = board[i][j];  
     if (!root->next.count(c)) return;  
     if (root->next[c]->isWord) {  
       res.push_back(root->next[c]->word);  
       root->next[c]->isWord = false;  
     }  
     visited[i][j] = true;  
     for (auto o : offset) {  
       int ii = i + o.first, jj = j + o.second;  
       if (ii >= 0 && ii < M && jj >= 0 && jj < N && !visited[ii][jj]) {  
         dfs(board, visited, ii, jj, root->next[board[i][j]], res);  
       }  
     }  
     visited[i][j] = false;  
   }  
     
   vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
     if (words.empty()) return {};  
     TrieNode* root = NULL;  
     for (auto s : words) {  
       insert(root, s);  
     }  
     vector<string> res;  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool>> visited(M, vector<bool>(N,false));  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         dfs(board, visited,i,j,root,res);  
       }  
     }  
     return res;  
   }  
 };  

199 Binary Tree Right Side View

来源：Leetcode

原帖：https://leetcode.com/problems/binary-tree-right-side-view/

题目：
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---
You should return [1, 3, 4].

代码：

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   void dfs(TreeNode* root, int level, vector<int>& res) {  
     if (!root) return;  
     if (res.size() == level) {  
       res.push_back(root->val);  
     } else {  
       res[level] = root->val;  
     }  
     dfs(root->left, level+1, res);  
     dfs(root->right, level+1, res);  
   }  
     
   vector<int> rightSideView(TreeNode* root) {  
     if (!root) return {};  
     vector<int> res;  
     dfs(root, 0, res);  
     return res;  
   }  
 };  

Find K Largest Elements in BST

来源：EPI

原帖：EPI 11.11. pg. 312.

题目：
Given the root of a BST and an integer k, design a function that finds the k largest elements in this BST. For example, if the input to your function is the BST in Figure 11.1 on Page 87 and k = 3, your function should return <53, 47, 43>.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
   
 void find_k_largest_in_BST_helper(TreeNode* root, int k, vector<int> &k_elements) {  
   if (!root || k_element.size() == k) {  
     return;  
   }  
   // Perform reverse inorder traversal  
   if (root && k_elements.size() < k) {  
     find_k_largest_in_BST_helper(root->right, k, k_elements);  
     if (k_elements.size() < k) {  
       k_elements.push_back(root->val);  
       find_k_largest_in_BST_helper(root->left, k, k_elements);  
     }  
   }  
 }  
   
 vector<int> find_k_largest_in_BST(TreeNode* root, int k) {  
   vector<int> k_elements;  
   find_k_largest_in_BST_helper(root, k , k_elements);  
   return k_elements;  
 }  

Serialize & Deserialize A Tree

来源：EPI, Facebook Interview

原帖：http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

题目：
A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back? For example,
         1
      /    \
     2      3
      \     /  
       4   5  
      /  \
     6    7

[Thoughts]
一个比较简单直接的做法是，通过前序遍历来做，把所有空节点当做“#”来标示。那么这棵树可以表示为
             1
          /     \
         2        3
       /   \     /   \
     #      4    5     #
          /   \
         6     7
        /  \  /  \
       #   # #    #
那么前序遍历的结果就是： {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下：
参考 http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

代码：

 // Tree serialize   
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void serialize(TreeNode* root, vector<char> &result) {  
   if (root == NULL) {  
     result.push_back('#'); // 表示终结结点  
     return;  
   }  
   result.push_back(root->val + '0');  
   serialize(root->left, result);  
   serialize(root->right, result);  
 }  
   
 // de-serialize  
 TreeNode* deserialize(const vector<char> &num, int &index) {  
   if (index >= num.size()) {  
    return NULL;  
   }   
   if (num[index] == '#') {  
     index++;  
     return NULL;  
   }  
   TreeNode *root = new TreeNode(num[index] -'0');  
   index++;  
   root->left = Deserialize(num, index);  
   root->right = Deserialize(num, index);  
   return root;  
 }  
   
 int main() {  
   vector<char> numbers = {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'};  
   int index = 0;  
   TreeNode* root = deserialize(number, index);  
   vector<char> res;  
   serialize(root, res);  
   return 0;  
 }  

Deserialize Tree的stack解法
EPI 6.8. pg. 236.
Reconstructing A Binary Tree From A Preorder Traversal With Marker. Design an O(n) time algorithm for reconstructing a binary tree from a preorder visit sequence that uses null to mark empty children. How would you modify your reconstruction algorithm if the sequence corresponded to a postorder or inorder walk.

代码：

 #define null 0;  
 TreeNode* reconstruct_preorder(const vector<int>& preorder) {  
   stack<TreeNode*> s;  
   // traversal back to forth  
   for (auto it = preorder.crbegin(); it != preorder.crend(); ++it) {  
     if (!(*it)) {  
       s.push(NULL);  
     } else {  
       TreeNode* l = s.top(); s.pop();  
       TreeNode* r = s.top(); s.pop();  
       TreeNode* root = new TreeNode(*it);  
       root->left = l;  
       root->right = r;  
       s.push(root);  
     }  
   }   
   return s.top();  
 }  

Perfect Binary Tree Node

来源：ITINT5

原帖：http://www.itint5.com/oj/#4

题目：
给定一棵完全二叉树的根结点，统计该树的结点总数。树结点类型名为TreeNode，您没必要知道该类型的定义，请使用下面的方法得到某个结点的左，右儿子结点，以及判断某结点是否为NULL。
//获得结点node的左儿子结点
TreeNode getLeftChildNode(TreeNode node);
//获得结点node的右儿子结点
TreeNode getRightChildNode(TreeNode node);
//判断结点node是否为NULL
int isNullNode(TreeNode node);

代码：

 // 树的高度，沿着左孩子  
 int getHeight(TreeNode node) {  
   int height = 0;  
   while (!isNullNode(node)) {  
     height++;  
     node = getLeftChildNode(node);  
   }  
   return height;  
 }  
   
 // 高度为height的满二叉树节点个数  
 int count_perfect_binary_tree_nodes(int height) {  
   return (int)pow(2, height) - 1;  
 }  
   
 int count_complete_binary_tree_nodes(TreeNode root) {  
   int count = 0;  
   while (!isNullNode(root)) {  
     int left = getHeight(getLeftChildNode(root));  
     int right = getHeight(getRightChildNode(root));  
     if (left == right) {  
       count += count_perfect_binary_tree_nodes(left) + 1;  
       root = getRightChildNode(root);  
     } else {  
       count += count_perfect_binary_tree_nodes(right) + 1;  
       root = getLeftChildNode(root);  
     }  
   }  
   return count;  
 }  

Min-BST

来源：EPI

原帖：EPI 11.6 pg. 307

题目：
A min-first BST is one in which the minimum key is stored at the root; each key in the left subtree is less than every key in the right subtree. The subtress themselves are min-first BSTs. Write a function that takes a min-first BST T and a key k, and returns true iff T contains k.

代码：

 class TreeNode {  
 public:  
   int data;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
   
 bool search_min_first_BST(TreeNode* r, int k) {  
   if (!r || r->data > k) {  
     return false;  
   } else if (r->data == k) {  
     return true;  
   } else if (search_min_first_BST(r->left, k)) {  
     return true;  
   }  
   return (!r->left || r->left->data < k) && search_min_first_BST(r->right, k);  
 }  

K Balanced Tree

来源：EPI

原帖：EPI 6.2. pg. 230

题目：
Define a node in a binary tree to be k-balanced if the difference in the number of nodes in its left and right subtrees is no more than k. Design an algorithm that takes as input a binary tree and positive
integer k, and returns a node u in the binary tree such that u is not k-balanced, but all of u's descendants are k-balanced. If no such node exists, return null. For example, when applied to the binary tree in Figure 6.1 on Page 55, your algorithm should return Node J if k = 3.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 pair<TreeNode*, int> find_non_k_balanced_node_helper(TreeNode* root, int k) {  
   // Empty tree  
   if (!root) {   
     return {NULL, 0};  
   }  
   // Early return if left subtree is not k-balanced  
   auto L = find_non_k_balanced_node_helper(root->left, k);  
   if (L.first) {  
     return L;  
   }  
   // Early return if right subtree is not k-balanced  
   auto R = find_non_k_balanced_node_helper(root->right, k);  
   if (R.first) {  
     return R;  
   }  
   int node_num = L.second + R.second + 1; // #nodes in n  
   if (abs(L.second - R .second) > k) {  
     return {root, node_num};  
   }  
   return {NULL, node_num};  
 }  
   
 TreeNode* find_non_k_balanced_node(TreeNode* root, int k) {  
   return find_non_k_balanced_node_helper(root, k).first;  
 }  
   

Convert BST To Double Linked List

来源：EPI

原帖：EPI 11.9; EPI 6.9;

题目：
Design an algorith that takes as input a BST B and returns a sorted doubly linked list on the same elements. Your algorithm should not allocate any new nodes. The original BST does not have to be preserved; use its nodes as the nodes of the resulting list, as shown in Figure 11.4 on the previous page.

代码：

 // convert binary search tree to double linked list  
 struct TreeNode {  
   int val;  
   TreeNode* left;   
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void bst2dll(TreeNode* root, TreeNode* &head, TreeNode* &tail) {  
   if (!root) return;  
   bst2dll(root->left, head, tail);  
   if (!head) {  
     head = tail = root;  
   } else {  
     tail->right = root;  
     root->left = tail;  
     tail = root;  
   }  
   TreeNode* right = root->right;  
   root->right = NULL;  
   bst2dll(right, head, tail);  
 }  
   
 TreeNode* bst2dll(TreeNode* root) {  
   TreeNode *head = NULL, *tail = NULL;  
   bst2dll(root, head, tail);  
   return head;  
 }  

Construct Binary Tree from Inorder and Postorder Traversal

来源：

原帖：https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题目：
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
   
 // 69ms  
 class Solution {  
 public:  
   TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {  
     return buildTreeHelper(inorder.begin(), postorder.begin(), inorder.size());  
   }  
   
   TreeNode *buildTreeHelper(vector<int>::iterator inorder, vector<int>::iterator postorder, int length) {  
     if (length <= 0) return NULL;  
     auto it = find(inorder, inorder + length, *(postorder + length - 1));  
     int left_len = it - inorder;  
     TreeNode *root = new TreeNode(*(postorder + length - 1));  
     root->left = buildTreeHelper(inorder, postorder, left_len);  
     root->right = buildTreeHelper(inorder + left_len + 1, postorder + left_len, length - left_len - 1);  
     return root;  
   }  
 };  
   
 // 25 ms using hashmap  
 class Solution {  
 public:  
   TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {  
     if(inorder.size() != postorder.size()) return NULL;  
     unordered_map<int, int> idx;  
     for(int i=0; i<inorder.size(); i++){  
       idx[inorder[i]] = i;  
     }  
     return build(inorder, postorder, 0, 0, inorder.size(), idx);  
   }  
     
   TreeNode *build(vector<int> &inorder, vector<int> &postorder, int ii, int pi, int N, unordered_map<int, int> &idx){  
     if(N == 0) return NULL;  
     int r = postorder[pi+N-1], lN = idx[r] - ii, rN = N-lN-1;  
     TreeNode *root = new TreeNode(r);  
     root->left = build(inorder, postorder, ii, pi, lN, idx);  
     root->right = build(inorder, postorder, ii+lN+1, pi+lN, rN, idx);  
     return root;  
   }  
 };  
   

Construct Binary Tree from Preorder and Inorder Traversal

来源：Leetcode

原帖：https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目：
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {  
     if (preorder.size() != inorder.size()) return NULL;  
     return buildTreeHelper(preorder.begin(), inorder.begin(), preorder.size());  
   }  
   
   TreeNode *buildTreeHelper(vector<int>::iterator preorder, vector<int>::iterator inorder, int length) {  
     if (length <= 0) return NULL;  
     auto it = find(inorder, inorder + length, *preorder);  
     int ll = it - inorder, rl = length - ll - 1;  
     TreeNode *root = new TreeNode(*preorder);  
     root->left = buildTreeHelper(preorder + 1, inorder, ll);  
     root->right = buildTreeHelper(preorder + 1 + ll, inorder + ll + 1, rl);  
     return root;  
   }  
 };  
     
 class Solution {  
 public:  
   typedef vector<int>::iterator ITERATOR;  
   TreeNode* buildTreeHelper(ITERATOR preorder, ITERATOR inorder, int length, unordered_map<int, ITERATOR>& map) {  
     if (length <= 0) return NULL;  
     auto it = map[*preorder];  
     int ll = it - inorder, rl = length - ll - 1;  
     TreeNode* root = new TreeNode(*preorder);  
     root->left = buildTreeHelper(preorder+1, inorder, ll, map);  
     root->right = buildTreeHelper(preorder+1+ll, inorder+ll+1, rl, map);  
     return root;  
   }  
   
   TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {  
     if (preorder.size() != inorder.size()) return NULL;  
     unordered_map<int, ITERATOR> map;  
     for (auto it = inorder.begin(); it != inorder.end(); ++it) {  
       map[*it] = it;  
     }  
     return buildTreeHelper(preorder.begin(), inorder.begin(), preorder.size(), map);  
   }  
 };  
   

Determine K-th Node In An Inorder Traversal

来源：EPI, Facebook Onsite

原帖：EPI 6.6 pg. 233

题目：
It is trivial to find the k-th node that appears in an inorder traversal with O(n) time complexity. However, with additional information on each node, you can do better. Design a function that efficiently computes the k-th node appearing in an inorder traversal. Specifically, your function should take as input a binary tree T and an integer k. Each node has a size field, which is the number of nodes in the subtree rooted at that node. What is the time complexity of your function?

代码：

 //Part I: TreeNodeSize  
 struct TreeNodeSize {  
   int val;  
   int size;  
     TreeNodeSize* left;  
     TreeNodeSize* right;  
     TreeNodeSize(int v) : data(d), size(1), left(NULL), right(NULL) {}  
 };  
   
 // Each node with a size variable  
 TreeNodeSize* find_kth_node_binary_tree(TreeNodeSize* root, int k) {  
   while (root && k) {  
     int left_size = root->left ? root->left->size : 0;  
     if (left_size < k - 1) {  
       k -= (left_size + 1);  
       root = root->right;  
     } else if (left_size == k - 1) {  
       return root;  
     } else {  
       root = root->left;  
     }  
   }  
   return NULL;  
   //throw length_error("no k-th node in binary tree");  
 }  
   
 //Part II: TreeNode structure  
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 TreeNode* find_kth_node(TreeNode* root, int k, int& n) {  
   if (!root) return NULL;  
   TreeNode* node = find_kth_node(root->left, k, n);  
   if (node) return node;  
   n += 1;  
   if (n == k) return root;  
   return find_kth_node(root->right, k, n);  
 }  
   
 TreeNode* find_kth_node_binary_tree(TreeNode* root, int k) {  
   int n = 0;  
   return find_kth_node(root, k, n);  
 }  
   

Form A Linked List From the Leaves Of A Binary Tree

来源：EPI

原帖：EPI 6.10 pg. 237.

题目：
Given a binary tree, write a function which forms a linked list from the leaves of the binary tree. The leaves should appear in left-to-right order. For example, when applied to the binary tree in Figure 6.1 on Page 55, your function should return <D, E, H, M, N, P>.

代码：

 struct BinaryTree {  
   int data;  
   BinaryTree* left;  
   BinaryTree* right;  
   BinaryTree(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
 void connect_leaves_helper(BinaryTree* root, list<BinaryTree*>& l) {  
   if (root) {  
     if (!root->left && !root->right) {  
       l.push_back(root);  
       return;  
     } else {  
       connect_leaves_helper(root->left, l);  
       connect_leaves_helper(root->right, l);  
     }  
   }  
 }  
   
 vector<BinaryTree*> connect_leaves(BinaryTree* root) {  
   vector<BinaryTree*> L;  
   connect_leaves_helper(root, L);  
   return L;  
 }  

Search Range in a Binary Search Tree

来源：G4G

原帖：http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

题目：
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order. For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

Algorithm:
1) If value of root’s key is greater than k1, then recursively call in left subtree.
2) If value of root’s key is in range, then print the root’s key.
3) If value of root’s key is smaller than k2, then recursively call in right subtree.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void searchRangeHelper(TreeNode* root, int k1, int k2, vector<int> &result) {  
   if (!root) return;  
   /* Since the desired o/p is sorted, recurse for left subtree first  
    If root->val is greater than k1, then only we can get o/p keys in left subtree */  
   if (root->val > k1) {  
     searchRangeHelper(root->left, k1, k2, result);  
   }    
   /* if root's val lies in range, then prints root's val */  
   if (root->val >= k1 && root->val <= k2) {  
     result.push_back(root->val);  
   }  
   /* If root->val is smaller than k2, then only we can get o/p keys in right subtree */  
   if (root->val < k2) {  
     searchRangeHelper(root->right, k1, k2, result);  
   }  
 }  
   
 vector<int> searchRange(TreeNode* root, int k1, int k2) {  
   vector<int> result;  
   searchRangeHelper(root, k1, k2, result);  
   return result;  
 }  

Search BST For The First Key Larger Than K

来源：EPI

原帖：EPI 11.5

题目：
Write a function that takes a BST T and a key k, and returns the first entry larger than k that would appear in an order walk. If k is absent or no key larger than k is present, return null. For example, when applied to the BST in Figure 11.1 on the previous page you should return 29 if k = 23; if k = 32, your should return null.

代码：

 struct TreeNode {  
   int data;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
 TreeNode* find_first_larger_k_with_k_exist(TreeNode* r, int k) {  
   bool found_k = false;  
   TreeNode* first = NULL;  
   while (r) {  
     if (r->data == k) {  
       found_k = true;  
       r = r->right;  
     } else if (r->data > k) {  
       first = r;  
       r = r->left;  
     } else { // r->data < k  
       r = r->right;  
     }  
   }  
   return found_k ? first : NULL;  
 }  

Search A BST For First Occurrence Of k

来源：EPI

原帖：EPI 11.4

题目：
Given a BST T, write recursive and iterative versions of a function that takes a BST T, a key k, and returns the node containing k that would appear first in an inorder walk. If k is absent, return null. For example, when applied to the BST in Figure 11.2 on the following page, your algorithm should return Node B if k = 108, Node G if k = 285, and null if k = 143.

代码：

 struct TreeNode {  
     int data;  
     TreeNode* left;  
     TreeNode* right;  
     TreeNode(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
 //Version 1: recursion  
 TreeNode* find_first_equal_k(TreeNode* r, int k) {  
     if (!r) {  
         return NULL; // no match  
     } else if (r->data == k) {  
         // Recursively search the left subtree for first one == k  
         TreeNode* n = find_first_equal_k(r->left, k);  
         return n ? n : r;  
     }   
     // Search left or right tree according to r->data and k  
     return find_first_equal_k(r->data < k ? r->right : r->left, k);  
 }  
   
 // Version 2: iteration  
 TreeNode* find_first_equal_k(TreeNode* r, int k) {  
     while (r) {  
         if (r->data < k) {  
             r = r->right;  
         } else if (r->data > k) {  
             r = r->left;  
         } else { // r->data == k  
             // Search for the leftmost in the left subtree  
             TreeNode* l = r->left;  
             while (l && l->data == k) {  
                 r = l;  
                 l = l->left;  
             }  
             return r;  
         }  
     }  
     return NULL; // not match  
 }  

208 Implement Trie (Prefix Tree)

来源：Leetcode

原帖：https://leetcode.com/problems/implement-trie-prefix-tree/

题目：
Implement a trie with insert, search, and startsWith methods.


代码：

 class TrieNode {  
 public:  
   // Initialize your data structure here.  
   TrieNode(bool word = false) {  
     isWord = word;  
   }  
   bool isWord;  
   unordered_map<char,TrieNode*> next;  
 };  
   
 class Trie {  
 public:  
   Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   void insert(string s) {  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
       if (i == s.size()-1) cur->isWord = true;  
     }  
   }  
   
   // Returns if the word is in the trie.  
   bool search(string key) {  
     if (key.empty()) return false;  
     TrieNode* cur = root;  
     for (int i = 0; i < key.size(); ++i) {  
       if (!cur->next.count(key[i]))   
         return false;  
       cur = cur->next[key[i]];  
     }  
     return cur->isWord ? true : false;  
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   bool startsWith(string prefix) {  
     if (prefix.empty()) return false;  
     TrieNode* cur = root;  
     for (int i = 0; i < prefix.size(); ++i) {  
       if (!cur->next.count(prefix[i]))   
         return false;  
       cur = cur->next[prefix[i]];  
     }  
     return true;  
   }  
   
 private:  
   TrieNode* root;  
 };  
   
 // Your Trie object will be instantiated and called as such:  
 // Trie trie;  
 // trie.insert("somestring");  
 // trie.search("key");  

扩展问题：

 /*  
  Shortest Unique Prefix *  
  Trie node  
  Given a string s and a set of strings D, find the shortest prefix of s   
  which is not a prefix of any string in D.  
  Example:  
  If s = "cat" and D = {"dog", "be", "cut"} return "ca"  
  If s = "cat" and D = {"dog", "be", "cut", "car"} return "cat"  
  If s = "cat" and D = {"dog", "be", "cut", "car", "cat"} return \epsilon   
 */  
   
 struct TrieNode {  
   bool isString;  
   unordered_map<char, TrieNode*> next; // TreeNode* hash[26];  
   TrieNode(bool _isString = false) : isStirng(_isString) {}  
 };  
   
 class Trie {  
 private:  
  TrieNode* root;  
   
 public:  
  Trie() {  
   root = new TrieNode();  
  }  
   
  bool insert(const string& s) {  
   TrieNode* p = root;  
   for (const char &c : s) {  
    if (p->next.find(c) == p->next.end()) {  
     p->next[c] = new TrieNode(false);  
    }  
    p = p->next[c];  
   }  
   // s already existed in this trie  
   if (p->isString == true) {  
    return false;  
   } else { // p->isString == false  
    p->isString = true; // inserts s into this trie  
    return true;  
      }  
  }  
   
  string getShortestUniquePrefix(const string& s) {  
   TrieNode* p = root;  
   string prefix = "";  
   for (auto& c : s) {  
    prefix += c;  
    if (p->next.find(c) == p->next.end()) {  
     return prefix;  
    }  
    p = p->next[c];  
   }  
   return "";   
  }  
 };  
   
   
 string find_shortest_prefix(const string& s, const unordered_set<string>& D) {  
  // Build a trie according to given dictionary D  
  Trie T;  
  for (const string &world : D) {  
   T.insert(world);  
  }  
  return T.getShortestUniquePrefix(s);  
 }  

Populating Next Right Pointers in Each Node II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

题目：
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
 You may only use constant extra space.
 For example,
 Given the following binary tree,
     1
    /  \
   2    3
  / \    \
 4   5    7
After calling your function, the tree should look like:
     1 -> NULL
    /  \
   2 -> 3 -> NULL
  / \    \
 4-> 5 -> 7 -> NULL

代码：

 /**  
  * Definition for binary tree with next pointer.  
  * struct TreeLinkNode {  
  * int val;  
  * TreeLinkNode *left, *right, *next;  
  * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   //Iteration: level by level  
   void connect(TreeLinkNode *root) {  
     if (!root) return;  
     TreeLinkNode *cur = root;  
     while (cur) { // level starting point  
       TreeLinkNode* level = cur;  
       TreeLinkNode* last = NULL;  
       cur = NULL;  
       while (level) { // level trarverse  
         TreeLinkNode *left = level->left;  
         TreeLinkNode* right = level->right;  
         if (!cur && (left || right)) {  
           cur = left ? left : right;  
         }  
         if (left) {  
           if (last) last->next = left;  
           last = left;  
         }  
         if (right) {  
           if (last) last->next = right;  
           last = right;  
         }  
         level = level->next;  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:    
   //Iterative BFS + Queue  
   void connect(TreeLinkNode *root) {  
     if (!root) return;  
     queue<TreeLinkNode*> q;  
     q.push(root);  
     TreeLinkNode *last = NULL;  
     while (!q.empty()) {  
       int size = q.size();  
       last = NULL;  
       for (int i = 0; i < size; ++i) {  
         TreeLinkNode* node = q.front(); q.pop();  
         if (last) last->next = node;  
         last = node;  
         if (node->left) {  
           q.push(node->left);  
         }  
         if (node->right) {  
           q.push(node->right);  
         }  
       }  
     }  
   }  
 };  
   
 // recursion  
 class Solution {  
 public:  
   void connect(TreeLinkNode *root) {  
     if(!root) return;  
     TreeLinkNode *p = root->next;  
     while(p){  
       if(p->left){  
         p = p->left;  
         break;  
       }  
       if(p->right){  
         p = p->right;  
         break;  
       }  
       p = p->next;  
     }  
     if(root->right)  
       root->right->next = p;  
     if(root->left)  
       root->left->next = root->right ? root->right : p;  
     connect(root->right);  
     connect(root->left);  
   }  
 };  

Populating Next Right Pointers in Each Node I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/

题目：
Given a binary tree
struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
      1
     /  \
   2     3
  / \     / \
 4  5  6  7
After calling your function, the tree should look like:
      1  ->  NULL
     /    \
   2 ->  3 -> NULL
  / \       / \
 4->5->6->7 -> NULL

代码：

 /**  
  * Definition for binary tree with next pointer.  
  * struct TreeLinkNode {  
  * int val;  
  * TreeLinkNode *left, *right, *next;  
  * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   void connect(TreeLinkNode *root) {  
     while (root) {  
       TreeLinkNode *level = root;  
       TreeLinkNode *last = NULL;       
       while (level && level->left) {  
         if (last) {  
           last->next = level->left;            
         }  
         level->left->next = level->right;  
         last = level->right;  
         level = level->next;  
       }  
       root = root->left;  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   void connect(TreeLinkNode *root) {  
     if(!root) return;  
     if(root->left)  
       root->left->next = root->right;  
     if(root->right && root->next)  
       root->right->next = root->next->left;  
     connect(root->left);  
     connect(root->right);  
   }  
 };  
   
 class Solution {  
 public:  
   void connect(TreeLinkNode *root) {  
     if(!root) return;  
     queue<TreeLinkNode*> Q;  
     Q.push(root);  
     while(!Q.empty()){  
       TreeLinkNode* p = Q.front();  
       Q.pop();  
       if(p->left){  
         p->left->next = p->right;  
         Q.push(p->left);  
       }  
       if(p->right){  
         if(p->next)  
           p->right->next = p->next->left;  
         Q.push(p->right);  
       }  
     }  
   }  
 };  

Recover Binary Search Tree

来源：Leetcode

原帖：http://oj.leetcode.com/problems/recover-binary-search-tree/

题目：
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

代码：

 struct TreeNode {  
   int val;  
   TreeNode *left;  
   TreeNode *right;  
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
 };  
   
 class Solution {  
 public:  
   //inorder traversal, space O(n)  
   void inorderTraversal(TreeNode *root, vector<TreeNode*> &inorder) {  
     if (!root) return;  
     inorderTraversal(root->left, inorder);  
     inorder.push_back(root);  
     inorderTraversal(root->right, inorder);  
   }  
   
   // 1, 2, 3, 4, 5 -> 1, 3, 2, 4, 5  
   // 1, 2, 3, 4, 5 -> 1, 4, 3, 2, 5  
   void recoverTree(TreeNode *root) {  
     vector<TreeNode *> inorder;  
     inorderTraversal(root, inorder);  
     TreeNode *first = NULL, *second = NULL;  
     for (int i = 1; i < inorder.size(); ++i) {  
       if (inorder[i - 1]->val < inorder[i]->val) {  
         continue;          
       }  
       if (!first) first = inorder[i - 1];  
       second = inorder[i]; // seceond must be fixed when first = NULL  
     }  
     swap(first->val, second->val); // swap values  
   }  
 };  
   
 class Solution {  
 public:  
   //Inorder traversal with 2 pointers  
   void recoverTree(TreeNode *root) {  
     TreeNode* prev = NULL, *first = NULL, *second = NULL;  
     recoverTreeHelper(root, prev, first, second);  
     swap(first->val, second->val);  
   }  
   
   void recoverTreeHelper(TreeNode* root, TreeNode* &prev, TreeNode* &first, TreeNode* &second) {  
     if (root == NULL) return;  
     //if (first && second) return; // BUG! find 2 pointers.  
     recoverTreeHelper(root->left, prev, first, second);  
     if (prev && prev->val > root->val) {  
       if (first == NULL) first = prev;          
       second = root; //两种情况, 相邻或者不相邻的两个点置换, 无论哪一种, 这个都可以cover.  
     }  
     prev = root;  
     recoverTreeHelper(root->right, prev, first, second);  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 3: Morris tree, inorder traversal  
   void recoverTree(TreeNode *root) {  
     TreeNode *cur = root, *prev = NULL;  
     TreeNode *first = NULL, *second = NULL, *last = NULL;  
     while (cur) {  
       if (cur->left == NULL) {  
         compare(last, cur, first, second);  
         last = cur;  
         cur = cur->right;  
       } else {  
         prev = cur->left;  
         while (prev->right != NULL && prev->right != cur) {  
           prev = prev->right;            
         }  
   
         if (prev->right == NULL) {  
           prev->right = cur;  
           cur = cur->left;  
         } else {  
           compare(last, cur, first, second);  
           last = cur;  
           prev->right = NULL;  
           cur = cur->right;  
         }  
       }  
     }  
     swap(first->val, second->val);  
   }  
   
   void compare(TreeNode *last, TreeNode *cur, TreeNode *&first, TreeNode *&second) {  
     if (last && last->val > cur->val) {  
       if (!first) first = last;  
       second = cur;  
     }  
   }  
 };  
   

Unique Binary Search Trees II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/unique-binary-search-trees-ii/

题目：
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
 For example,
 Given n = 3, your program should return all 5 unique BST's shown below.
 1         3     3      2      1
  \         /     /       / \       \
   3     2     1      1   3      2
  /      /       \                      \
 2     1         2                    3

代码：

 class Solution {  
 public:  
   vector<TreeNode*> generateTrees(int n) {  
     return generateTreesHelper(1, n);  
   }  
   
   vector<TreeNode*> generateTreesHelper(int start, int end) { // 1...n, left = 1, right = n  
     vector<TreeNode*> res;  
     if (start > end) {  
       res.push_back(NULL);  
       return res;  
     }  
     for (int k = start; k <= end; k++) { // root starts from k; 拆分成不同left, right subtree  
       auto leftTrees = generateTreesHelper(start, k - 1);  
       auto rightTrees = generateTreesHelper(k + 1, end);  
       for (int i = 0; i < leftTrees.size(); i++) {  
         for (int j = 0; j < rightTrees.size(); j++) {  
           TreeNode* root = new TreeNode(k);  
           root->left = leftTrees[i]; // concatenate into left or right  
           root->right = rightTrees[j];  
           res.push_back(root);  
         }  
       }  
     }  
     return res;  
   }  
 };