fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. int val;
  5. vector<TreeNode*>child;
  6. TreeNode(int val):child({}),val(val){};
  7. };
  8. TreeNode* constructTree(vector<int>&arr){
  9. if(arr[0]==-1)return nullptr;
  10. TreeNode* root = new TreeNode(arr[0]);
  11.  
  12. stack<TreeNode*>st;
  13. st.push(root);
  14.  
  15. for(int i = 1;i<arr.size();i++){
  16. if(arr[i]!=-1){
  17. TreeNode* par = st.top();
  18. TreeNode* newChild = new TreeNode(arr[i]);
  19. par->child.push_back(newChild);
  20. st.push(newChild);
  21. }else{
  22. st.pop();
  23. }
  24. }
  25. return root;
  26. }
  27. int height(TreeNode* root){
  28. if(!root )return -1;
  29. // if(!root->child)return 1;
  30. //int mx = root->val;
  31. int mx = -1;
  32. for(auto child: root->child){
  33. int maximum = height(child);
  34. mx = max(maximum,mx);
  35. }
  36. return 1+mx;
  37. }
  38. void displayTree(TreeNode* root){
  39. if(root)cout<<root->val<<"->";
  40.  
  41. for(auto child : root->child)cout<<child->val<<",";
  42. cout<<"."<<endl;
  43. for(auto child : root->child)displayTree(child);
  44. }
  45. int main() {
  46. //-1 for going up to the par then down to its next child
  47. //vector<int>arr = {10,20,50,-1,60,-1,-1,30,70,-1};
  48. vector<int>arr = {10,20,50,-1,60,-1,-1,30,70,-1,80,100,-1,110,-1,-1,90,-1,-1,40,120,-1,130,-1,-1,-1};
  49. TreeNode* root = constructTree(arr);
  50. //displayTree(root);
  51. cout<<height(root);
  52. return 0;
  53. }
Success #stdin #stdout 0s 544KB
stdin
Standard input is empty
stdout
3