编程练习题: 找出N叉树的深度

学编程

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

n-ary-tree

上面这颗树, 深度为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; // children depth plus one
    }
};

广度优先 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)); // push children to queue
                depth = max(p.second + 1, depth);   // record the maximum depth of current node
            }
        }
        return depth;
    }
};

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

英文: C++ Coding Exercise – Find Maximum Depth of N-ary Tree