269. Alien Dictionary

I didn't have any clue in first place. So I followed the top rated solution which uses a topology sort algorithm. I made mistakes in
line 12: I was thinking that all the words should follow the same rule pair by pair. So I did two for loops in first place. However, it seems not. This is a typical question that need to be clarified in an interview.
line 13-14: I didn't have these two rows in first place. However, it turns out to be critical otherwise you'll miss those isolated vertices nodes in the graph. For example "wrf" "e". If you don't have these two line, you'll miss "r" and "f" these two nodes.
line 11 & 15: the found variable is really needed. I broke out the second for loop once I found the first different letter in two words. However, that’ll miss the other present letters in the rest of two words.

1:  class Solution {  
2:  public:  
3:    string alienOrder(vector<string>& words) {  
4:      if (words.size() == 0) return "";  
5:      if (words.size() == 1) return words[0];  
6:      // build graph  
7:      unordered_map<char, set<char>> graph;  
8:      for (int i = 0; i+1 < words.size(); i++) {  
9:        string word1 = words[i];  
10:        string word2 = words[i+1];  
11:        bool found = false;  
12:        for (int j = 0; j < max(word1.size(), word2.size()); j++) {  
13:          if (j < word1.size() && graph.find(word1[j]) == graph.end()) graph[word1[j]] = set<char>();  
14:          if (j < word2.size() && graph.find(word2[j]) == graph.end()) graph[word2[j]] = set<char>();  
15:          if (j < word1.size() && j < word2.size() && word1[j] != word2[j] && !found) {  
16:            graph[word1[j]].insert(word2[j]);  
17:            found = true;  
18:          }  
19:        }  
20:      }  
21:      // start topology sort  
22:      vector<bool> visited(26, false);  
23:      vector<bool> path(26, false);  
24:      string res;  
25:      for (auto it = graph.begin(); it != graph.end(); it++) {  
26:        if (!visited[it->first-'a'] && hasCycle(graph, it->first, visited, path, res)) return "";  
27:      }  
28:      reverse(res.begin(), res.end());  
29:      return res;  
30:    }  
31:    bool hasCycle(unordered_map<char, set<char>> &graph, char c, vector<bool> &visited, vector<bool> &path, string &res) {  
32:      if (visited[c-'a']) return false;  
33:      visited[c-'a'] = path[c-'a'] = true;  
34:      for (auto it = graph[c].begin(); it != graph[c].end(); it++) {  
35:        if (path[*it-'a'] || hasCycle(graph, *it, visited, path, res)) return true;  
36:      }  
37:      path[c-'a'] = false;  
38:      res += c;  
39:      return false;  
40:    }  
41:  };  

104. Maximum Depth of Binary Tree

A classic DFS solution on tree again.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int maxDepth(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      return 1 + max(maxDepth(root->left), maxDepth(root->right));  
15:    }  
16:  };  

100. Same Tree

Well, very straightforward DFS solution.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool isSameTree(TreeNode* p, TreeNode* q) {  
13:      if (p == NULL && q== NULL) return true;  
14:      if (p == NULL && q != NULL || p != NULL && q == NULL || p->val != q->val) return false;  
15:      return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);  
16:    }  
17:  };  

110. Balanced Binary Tree

Not much to say, a classic DFS solution on tree.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool isBalanced(TreeNode* root) {  
13:      if (root == NULL) return true;  
14:      if (abs(depth(root->left) - depth(root->right)) > 1) return false;  
15:      return isBalanced(root->left) && isBalanced(root->right);  
16:    }  
17:    int depth(TreeNode *root) {  
18:      if (root == NULL) return 0;  
19:      return 1 + max(depth(root->left), depth(root->right));  
20:    }  
21:  };  

101. Symmetric Tree

Well, pretty straightforward DFS solution.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool isSymmetric(TreeNode* root) {  
13:      if (root == NULL) return true;  
14:      return helper(root->left, root->right);  
15:    }  
16:    bool helper(TreeNode *p, TreeNode *q) {  
17:      if (p == NULL && q == NULL) return true;  
18:      if (p == NULL && q != NULL || p != NULL && q == NULL || p->val != q->val) return false;  
19:      return helper(p->left, q->right) && helper(p->right, q->left);  
20:    }  
21:  };  

112. Path Sum

Well, pretty straightforward DFS solution

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool hasPathSum(TreeNode* root, int sum) {  
13:      if (root == NULL) return false;  
14:      if (root->left == NULL && root->right == NULL) return sum == root->val;  
15:      return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);  
16:    }  
17:  };  

111. Minimum Depth of Binary Tree

I was computing the depth from bottom to top which means you’ll have many redundant calls because you call h times from the root to get the depth and you’ll call h-1 times again from the left child to a leaf. Actually the h-1 times can be avoided if we compute the depth from top to bottom.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  private:  
12:    int minD = INT_MAX;  
13:  public:  
14:    int minDepth(TreeNode* root) {  
15:      if (root == NULL) return 0;  
16:      helper(root, 1);  
17:      return minD;  
18:    }  
19:    void helper(TreeNode *root, int depth) {  
20:      if (root->left == NULL && root->right == NULL) { minD = min(minD, depth); return; }  
21:      if (root->left) helper(root->left, depth+1);  
22:      if (root->right) helper(root->right, depth+1);  
23:    }  
24:  };