create account

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

View this thread on: hive.blogpeakd.comecency.com
· @justyy · (edited)
$10.23
C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题:找出N叉树的深度
![](https://ipfs.busy.org/ipfs/QmfPN8W19QLM76b6UdUgKfFQvZ6niiF1VD4Zk4SqBC2LED)

> 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](https://ipfs.busy.org/ipfs/QmVcB8FG1fdD6NaZejAMZ3kUdKBKuvbEKfeiuR5CpwDubm)

> 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
```
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

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

## DFS (Depth First Search)
[DFS](https://helloacm.com/c-coding-exercise-sum-of-left-leaves-bfs-dfs-recursion/) is usually easy to implement using [recursion](https://helloacm.com/how-to-check-symmetric-tree-in-c-iterative-and-recursion/). The depth of N-ary tree is the maximum depth of its subtree (children) plus one. 

```
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 (Breadth First Search)
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.

```
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](https://helloacm.com/cc-coding-exercise-word-break-dp-bfs-dfs/) 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](https://steemit.com/witness-category/@justyy/justyy-just-another-witness) by 
1. voting me [here](https://steemconnect.com/sign/account_witness_vote?approve=1&witness=justyy), or
2. voting me as [a proxy](https://v2.steemconnect.com/sign/account-witness-proxy?proxy=justyy&approve=1).

Thank you! **Some of My Contributions: [SteemIt Tutorials, Robots, Tools and APIs](https://helloacm.com/tools/steemit/)**

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

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

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

![image.png](https://ipfs.busy.org/ipfs/QmVcB8FG1fdD6NaZejAMZ3kUdKBKuvbEKfeiuR5CpwDubm)

上面这颗树,深度为3.

## N叉树的C++定义
```
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

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

## 深度优先 DFS (Depth First Search)
用[递归](https://justyy.com/archives/6431)来实现深度优先最合适了。这题的解法就是递归的找出子树的深度,然后答案就是这些子树深度最深的那个加上一。

```
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就是答案
    }
};
```

## 广度优先 BFS (Breadth First Search)
[广度优先](https://justyy.com/archives/6433)一层一层的遍例树,可以用队列来实现,每次从队列中取出一个节点,然后把子树结点依次的添加到队列中并计算当前深度。

```
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

## 支持我的工作 支持我成为 [见证人](https://steemit.com/cn/@justyy/5h6gyv-cn) 
1. [请在 这里 投我一票](https://steemconnect.com/sign/account_witness_vote?approve=1&witness=justyy), 或者
2. 设置我 [为代理](https://v2.steemconnect.com/sign/account-witness-proxy?proxy=justyy&approve=1).

谢谢您! 我的贡献:[SteemIt 工具、API接口、机器人和教程](https://helloacm.com/tools/steemit-tools/)

## 股东工具
1. 成为股东:[代理5 SP 即可 (退出股东 输入 0即可)](https://helloacm.com/tools/steemit/delegate-form/?delegatee=justyy)
2. [查询当前股东](https://helloacm.com/tools/steemit/list-of-delegators/?id=justyy)

请注意:每次代理都是以最后一次输入的SP数量为标准,比如已经代理10 SP,想多代理5 SP则需要输入 最后的数字 15 SP(而不是 5!)
👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 20 others
properties (23)
authorjustyy
permlinkc-coding-exercise-find-maximum-depth-of-n-ary-tree-n
categoryprogramming
json_metadata{"community":"busy","app":"steemit/0.1","format":"markdown","tags":["programming","coding-exercise","cn-programming","busy","coding"],"links":["https://helloacm.com/c-coding-exercise-sum-of-left-leaves-bfs-dfs-recursion/","https://helloacm.com/how-to-check-symmetric-tree-in-c-iterative-and-recursion/","https://helloacm.com/cc-coding-exercise-word-break-dp-bfs-dfs/","https://steemit.com/witness-category/@justyy/justyy-just-another-witness","https://steemconnect.com/sign/account_witness_vote?approve=1&witness=justyy","https://v2.steemconnect.com/sign/account-witness-proxy?proxy=justyy&approve=1","https://helloacm.com/tools/steemit/","https://helloacm.com/c-coding-exercise-find-maximum-depth-of-n-ary-tree/","https://justyy.com/archives/6431","https://justyy.com/archives/6433","https://justyy.com/archives/6444","https://steemit.com/cn/@justyy/5h6gyv-cn","https://helloacm.com/tools/steemit-tools/","https://helloacm.com/tools/steemit/delegate-form/?delegatee=justyy","https://helloacm.com/tools/steemit/list-of-delegators/?id=justyy"],"image":["https://ipfs.busy.org/ipfs/QmfPN8W19QLM76b6UdUgKfFQvZ6niiF1VD4Zk4SqBC2LED","https://ipfs.busy.org/ipfs/QmVcB8FG1fdD6NaZejAMZ3kUdKBKuvbEKfeiuR5CpwDubm"]}
created2018-08-05 11:09:09
last_update2018-08-05 20:11:36
depth0
children3
last_payout2018-08-12 11:09:09
cashout_time1969-12-31 23:59:59
total_payout_value8.622 HBD
curator_payout_value1.607 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length5,177
author_reputation280,616,224,641,976
root_title"C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题:找出N叉树的深度"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id67,179,719
net_rshares6,598,265,879,445
author_curate_reward""
vote details (84)
@gasparcha ·
Is there any in chinese that i'm not able to read in english? sry but my lenguage is limited to eng-spa-por and a little sign lenguage xD
properties (22)
authorgasparcha
permlinkre-justyy-c-coding-exercise-find-maximum-depth-of-n-ary-tree-n-20180806t082456353z
categoryprogramming
json_metadata{"community":"busy","app":"busy/2.5.4","format":"markdown","tags":["programming"],"users":[],"links":[],"image":[]}
created2018-08-06 08:25:00
last_update2018-08-06 08:25:00
depth1
children2
last_payout2018-08-13 08:25:00
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length137
author_reputation4,745,797,952,486
root_title"C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题:找出N叉树的深度"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id67,274,140
net_rshares0
@justyy ·
Hi, the first part is English and the second part is Chinese translation. it is bilingual.
👍  , , ,
properties (23)
authorjustyy
permlinkre-gasparcha-re-justyy-c-coding-exercise-find-maximum-depth-of-n-ary-tree-n-20180806t101908229z
categoryprogramming
json_metadata{"tags":["programming"],"app":"steemit/0.1"}
created2018-08-06 10:19:06
last_update2018-08-06 10:19:06
depth2
children1
last_payout2018-08-13 10:19:06
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length90
author_reputation280,616,224,641,976
root_title"C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题:找出N叉树的深度"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id67,282,254
net_rshares6,146,589,697
author_curate_reward""
vote details (4)
@gasparcha ·
Cool, So I'm not missing anything, well, besides the things my brain can't quite fully understand yet xD
Anyhow, thanks for the clases, wish i where proficient enough to get the 100% of them.
properties (22)
authorgasparcha
permlinkre-justyy-re-gasparcha-re-justyy-c-coding-exercise-find-maximum-depth-of-n-ary-tree-n-20180806t103659271z
categoryprogramming
json_metadata{"community":"busy","app":"busy/2.5.4","format":"markdown","tags":["programming"],"users":[],"links":[],"image":[]}
created2018-08-06 10:37:00
last_update2018-08-06 10:37:00
depth3
children0
last_payout2018-08-13 10:37:00
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length191
author_reputation4,745,797,952,486
root_title"C++ Coding Exercise - Find Maximum Depth of N-ary Tree - 编程练习题:找出N叉树的深度"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id67,283,523
net_rshares0