559. Maximum Depth of N-ary Tree

/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: int maxDepth(Node* root) { if (root == nullptr) return 0; vector<int> max_histories; // to store history of max arc at every leaf node stack<Node*> s; // for inorder traversal int counter = 0; // for count... Node *curr = root; while (!s.empty || curr){ // first check if curr is a leaf node if (curr->left == nullptr && curr->right == nullptr){ counter++; max_histories.push_back(counter); counter--; // go one step back curr = s.top(); s.pop(); } else if (curr->left == nullptr && curr->right != nullptr){ // current node does not have left child. Go to the right counter++; curr = curr->right; } else if (curr->left != nullptr && curr->left == nullptr){ // current node does not have right child. Go to the left counter++; curr = curr->left; } else { // current node has both left and right child! Bad bad bad. // use in-order traversal. push this node to stack first, then visit the left child. Then visit the right child. s.push(curr->right); s.push(curr); counter++; curr = curr->left; } } // now find the max element in vector int it = max_elements(max_histories.begin(), max_histories.end()); return it; };