编程练习题: 找出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;
    }
};

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

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

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

GD Star Rating
loading...

本文一共 179 个汉字, 你数一下对不对.

编程练习题: 找出N叉树的深度. (AMP 移动加速版本)
上一篇: C++ 编程练习题 - 找出第三大的数
下一篇: C++编程练习题: 找出字符串的所有大小小组合

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

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

N叉树的C++定义

深度优先 DFS (Depth First Search)

广度优先 BFS (Breadth First Search)

评论

N叉树的C++定义

深度优先 DFS (Depth First Search)

广度优先 BFS (Breadth First Search)

相关文章：

评论