366. Find Leaves of Binary Tree

I used hash map and DFS to solve this problem. Hash map is used to tag visited node. So the leaf becomes:
1. node->left == NULL && node->left == RIGHT
2. node->left == NULL && mp[node->right] = true
3. node->right == NULL && mp[node->left] = true
4. mp[node->left] == true && mp[node->right] == true

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:    unordered_map<TreeNode*, bool> mp;  
13:  public:  
14:    vector<vector<int>> findLeaves(TreeNode* root) {  
15:      vector<vector<int>> res;  
16:      if (root == NULL) return res;  
17:      while (!mp[root]) {  
18:        vector<int> leaves;  
19:        helper(root, leaves, res);  
20:        res.push_back(leaves);  
21:      }  
22:      return res;  
23:    }  
24:    void helper(TreeNode *root, vector<int> &leaves, vector<vector<int>> &res) {  
25:      if (root->left == NULL && root->right == NULL || mp[root->left] && mp[root->right] ||  
26:        root->left == NULL && mp[root->right] || mp[root->left] && root->right == NULL) {  
27:        leaves.push_back(root->val);  
28:        mp[root] = true;  
29:        return;  
30:      }  
31:      if (root->left && !mp[root->left]) helper(root->left, leaves, res);  
32:      if (root->right && !mp[root->right]) helper(root->right, leaves, res);  
33:      return;  
34:    }  
35:  };  

There is another concise way to solve this problem. We can basically save the node by levels if we know the level.

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:    vector<vector<int>> findLeaves(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      dfs(root, res);  
15:      return res;  
16:    }  
17:    int dfs(TreeNode* root, vector<vector<int>> &res) {  
18:      if (root == NULL) return 0;  
19:      int level = max(dfs(root->left, res), dfs(root->right, res)) + 1;  
20:      if (level > res.size()) res.push_back(vector<int>());  
21:      res[level-1].push_back(root->val);  
22:      return level;  
23:    }  
24:  };