nikunjsoni

366

Jul 1st, 2021
111
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. };
RAW Paste Data