#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
vector<TreeNode*>child;
TreeNode(int val):child({}),val(val){};
};
TreeNode* constructTree(vector<int>&arr){
if(arr[0]==-1)return nullptr;
TreeNode* root = new TreeNode(arr[0]);
stack<TreeNode*>st;
st.push(root);
for(int i = 1;i<arr.size();i++){
if(arr[i]!=-1){
TreeNode* par = st.top();
TreeNode* newChild = new TreeNode(arr[i]);
par->child.push_back(newChild);
st.push(newChild);
}else{
st.pop();
}
}
return root;
}
int height(TreeNode* root){
if(!root )return -1;
// if(!root->child)return 1;
//int mx = root->val;
int mx = -1;
for(auto child: root->child){
int maximum = height(child);
mx = max(maximum,mx);
}
return 1+mx;
}
void displayTree(TreeNode* root){
if(root)cout<<root->val<<"->";
for(auto child : root->child)cout<<child->val<<",";
cout<<"."<<endl;
for(auto child : root->child)displayTree(child);
}
int main() {
//-1 for going up to the par then down to its next child
//vector<int>arr = {10,20,50,-1,60,-1,-1,30,70,-1};
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};
TreeNode* root = constructTree(arr);
//displayTree(root);
cout<<height(root);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBUcmVlTm9kZXsKCWludCB2YWw7Cgl2ZWN0b3I8VHJlZU5vZGUqPmNoaWxkOwoJVHJlZU5vZGUoaW50IHZhbCk6Y2hpbGQoe30pLHZhbCh2YWwpe307Cn07ClRyZWVOb2RlKiBjb25zdHJ1Y3RUcmVlKHZlY3RvcjxpbnQ+JmFycil7CmlmKGFyclswXT09LTEpcmV0dXJuIG51bGxwdHI7ClRyZWVOb2RlKiByb290ID0gbmV3IFRyZWVOb2RlKGFyclswXSk7CgpzdGFjazxUcmVlTm9kZSo+c3Q7CnN0LnB1c2gocm9vdCk7Cgpmb3IoaW50IGkgPSAxO2k8YXJyLnNpemUoKTtpKyspewoJaWYoYXJyW2ldIT0tMSl7CgkJVHJlZU5vZGUqIHBhciA9IHN0LnRvcCgpOwoJCVRyZWVOb2RlKiBuZXdDaGlsZCA9IG5ldyBUcmVlTm9kZShhcnJbaV0pOwoJCXBhci0+Y2hpbGQucHVzaF9iYWNrKG5ld0NoaWxkKTsKCQlzdC5wdXNoKG5ld0NoaWxkKTsKCX1lbHNlewoJCXN0LnBvcCgpOwoJfQp9CnJldHVybiByb290Owp9CmludCBoZWlnaHQoVHJlZU5vZGUqIHJvb3QpewoJaWYoIXJvb3QgKXJldHVybiAtMTsKLy8JaWYoIXJvb3QtPmNoaWxkKXJldHVybiAxOwoJLy9pbnQgbXggPSByb290LT52YWw7CglpbnQgbXggPSAtMTsKCWZvcihhdXRvIGNoaWxkOiByb290LT5jaGlsZCl7CglpbnQgbWF4aW11bSA9IGhlaWdodChjaGlsZCk7CgkgbXggPSBtYXgobWF4aW11bSxteCk7Cgl9CglyZXR1cm4gMStteDsKfQp2b2lkIGRpc3BsYXlUcmVlKFRyZWVOb2RlKiByb290KXsKCWlmKHJvb3QpY291dDw8cm9vdC0+dmFsPDwiLT4iOwoJCglmb3IoYXV0byBjaGlsZCA6IHJvb3QtPmNoaWxkKWNvdXQ8PGNoaWxkLT52YWw8PCIsIjsKCWNvdXQ8PCIuIjw8ZW5kbDsKCWZvcihhdXRvIGNoaWxkIDogcm9vdC0+Y2hpbGQpZGlzcGxheVRyZWUoY2hpbGQpOwp9CmludCBtYWluKCkgewoJLy8tMSBmb3IgZ29pbmcgdXAgdG8gdGhlIHBhciB0aGVuIGRvd24gdG8gaXRzIG5leHQgY2hpbGQKLy92ZWN0b3I8aW50PmFyciA9IHsxMCwyMCw1MCwtMSw2MCwtMSwtMSwzMCw3MCwtMX07CnZlY3RvcjxpbnQ+YXJyID0gezEwLDIwLDUwLC0xLDYwLC0xLC0xLDMwLDcwLC0xLDgwLDEwMCwtMSwxMTAsLTEsLTEsOTAsLTEsLTEsNDAsMTIwLC0xLDEzMCwtMSwtMSwtMX07CglUcmVlTm9kZSogcm9vdCA9IGNvbnN0cnVjdFRyZWUoYXJyKTsKCS8vZGlzcGxheVRyZWUocm9vdCk7Cgljb3V0PDxoZWlnaHQocm9vdCk7CglyZXR1cm4gMDsKfQ==