(N叉树 DFS 递归 BFS) leetcode 559. Maximum Depth of N-ary Tree

佚名 6年前 (2019-04-26) 随笔 1006人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

--------------------------------------------------------------------------------------------------------------------------------------

这个和求二叉树的最大深度类似，只要掌握了二叉树的最大深度的解法以及理解了N叉树的原理，解决这个题就会很简单了。

递归/DFS：

C++代码：

/*
// 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 maxSum = 1;   //这个是必须的，不能写错。因为根节点的深度为1。
        for(Node *cur:root->children){
            maxSum = max(maxSum, 1 + maxDepth(cur));
        }
        return maxSum;
    }
};

BFS（迭代）:

C++代码：

/*
// 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;
        queue<Node*> q;
        q.push(root);
        int sum = 0;
        while(!q.empty()){
            sum++;
            for(int i = q.size(); i > 0 ; i--){
                auto t = q.front();
                q.pop();
                for(Node *cur : t->children){
                    q.push(cur);
                }
            }
        }
        return sum;
    }
};