C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题：找出N叉树的深度
programming
7 minutes read (About 1026 words)

C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题：找出N叉树的深度

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:

image.png

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.

Definition of N-ary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

DFS is usually easy to implement using recursion. The depth of N-ary tree is the maximum depth of its subtree (children) plus one. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) {
            return 0;
        }
        int depth = 0;
        for (const auto &subTree: root->children) {
            auto d = maxDepth(subTree);
            depth = max(depth, d);
        }
        return depth + 1; // children depth plus one
    }
};

BFS travels the tree level by level. This is done by maintaining a queue and expanding the children nodes node by node. At each iteration, we also need to calculate its depth and push the depth together with the node in the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) return 0;
        queue<pair<Node*, int>> Q;
        Q.push(make_pair(root, 1));
        int depth = 1;
        while (Q.size() > 0) {
            auto p = Q.front();
            Q.pop();
            for (const auto &n: p.first->children) {
                Q.push(make_pair(n, p.second + 1)); // push children to queue
                depth = max(p.second + 1, depth);   // record the maximum depth of current node
            }
        }
        return depth;
    }
};

Both BFS and DFS need to walk through the entire tree, and therefore, performance-wise, there is no much difference.

Support me and my work as a witness - witness thread by

  1. voting me here, or
  2. voting me as a proxy.

Thank you! Some of My Contributions: SteemIt Tutorials, Robots, Tools and APIs

// Reposted to my blog for better indexing: https://helloacm.com/c-coding-exercise-find-maximum-depth-of-n-ary-tree/

题意：找出N叉树的最大深度。

image.png

上面这颗树，深度为3.

N叉树的C++定义

1
2
3
4
5
6
7
8
9
10
11
12
13
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

用递归来实现深度优先最合适了。这题的解法就是递归的找出子树的深度，然后答案就是这些子树深度最深的那个加上一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) {
            return 0;
        }
        int depth = 0;
        for (const auto &subTree: root->children) {
            auto d = maxDepth(subTree);
            depth = max(depth, d);
        }
        return depth + 1; // 子树最大深度加1就是答案
    }
};

广度优先一层一层的遍例树，可以用队列来实现，每次从队列中取出一个节点，然后把子树结点依次的添加到队列中并计算当前深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) return 0;
        queue<pair<Node*, int>> Q;
        Q.push(make_pair(root, 1));
        int depth = 1;
        while (Q.size() > 0) {
            auto p = Q.front();
            Q.pop();
            for (const auto &n: p.first->children) {
                Q.push(make_pair(n, p.second + 1)); //子节点依次入队列
                depth = max(p.second + 1, depth);  // 记录并更新当前节点的深度
            }
        }
        return depth;
    }
};

两种方法都需要把整颗树走完才能算出最大深度，所以时间复杂度都是类似的。

// 同步到我的博客： https://justyy.com/archives/6444

支持我的工作 支持我成为 见证人

  1. 请在 这里 投我一票, 或者
  2. 设置我 为代理.

谢谢您！ 我的贡献：SteemIt 工具、API接口、机器人和教程

股东工具

  1. 成为股东：代理5 SP 即可 （退出股东 输入 0即可）
  2. 查询当前股东

请注意：每次代理都是以最后一次输入的SP数量为标准，比如已经代理10 SP，想多代理5 SP则需要输入 最后的数字 15 SP（而不是 5！）

This page is synchronized from the post: ‘C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题：找出N叉树的深度’

# busy, cn-programming, coding, coding-exercise, programming
【第 叁肆陆 期】Daily #CN Updates CN社区【收益排行榜】【CN区谁在POWER DOWN？】【优秀文章】【YY银行股东】(2018-08-06)
【第 叁肆伍 期】Daily #CN Updates CN社区【收益排行榜】【CN区谁在POWER DOWN？】【优秀文章】【YY银行股东】(2018-08-05)
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×