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

JustYY.com 小赖子的英国生活和资讯

6 years ago

阅读 桌面完整版

learn-to-code 编程练习题: 找出N叉树的深度 ACM题解数据结构与算法

学编程

题意: 找出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

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

N叉树的C++定义

深度优先 DFS (Depth First Search)

广度优先 BFS (Breadth First Search)

强烈推荐

相关文章：