# 366

Jul 1st, 2021
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. private:
14.     vector<vector<int>> solution;
15. public:
16.     int getHeight(TreeNode *root) {
17.         // return -1 for null nodes
18.         if (!root)
19.             return -1;
20.
21.         // first calculate the height of the left and right children
22.         int leftHeight = getHeight(root->left);
23.         int rightHeight = getHeight(root->right);
24.
25.         // based on the height of the left and right children, obtain the height of the current (parent) node
26.         int currHeight = max(leftHeight, rightHeight) + 1;
27.
28.         // create space for node located at `currHeight` if not already exists
29.         if(solution.size() == currHeight)
30.             solution.push_back({});
31.
32.         // insert the value at the correct position in the solution array
33.         solution[currHeight].push_back(root->val);
34.
35.         // return the height of the current node
36.         return currHeight;
37.     }
38.
39.     vector<vector<int>> findLeaves(TreeNode* root) {
40.         solution.clear();
41.         getHeight(root);
42.         return solution;
43.     }
44. };