Question

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

Difficulty:Easy

Category:Tree, Depth-First-Search, Breadth-First-Search

Analyze

So we use the template code for this Tree Question.

There are four steps for this template:

1. Boundary conditions.
2. Deal with the root value.
3. recursive call funciton
4. compare ouput value

Solution

/*
// 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;
    if (root->children.empty()) return 1;
    int len = root->children.size(), max_dep = 0;
    for (int i = 0; i < len; ++i) {
      int d = maxDepth(root->children[i]);
      max_dep = max(max_dep, d);
    }
    return max_dep + 1;
  }
};