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:

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 is usually easy to implement using 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 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

voting me here, or
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叉树的最大深度。

上面这颗树，深度为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)

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

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)

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

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;
    }
};