題目要求

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.
給定一個(gè)n-樹，求其最大深度。

舉例.PNG

題目分析

本題要求的一棵樹的最大深度，其實(shí)就是求一顆樹的深度，也可以理解成求根節(jié)點(diǎn)的深度，關(guān)于樹的深度請參考：樹。

所以可以將這個(gè)問題分冶。即將求一個(gè)節(jié)點(diǎn)的深度轉(zhuǎn)換成求其子節(jié)點(diǎn)的最大深度+1，這個(gè)思想可以用遞歸的方法來實(shí)現(xiàn)。

本題解析

/*
// 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 )
            return 0;

        int depth = 0;
        
        for( auto &child: root->children )
        {    /*遍歷子節(jié)點(diǎn)*/
            depth = max( depth, maxDepth(child));      /*求出子節(jié)點(diǎn)的最大深度*/
        }
        
        return depth + 1;    /*返回子節(jié)點(diǎn)的最大深度 + 1*/
        
    }
};