力扣-559题 N叉树的最大深度（C++）- 迭代+递归

悠悠 2022-09-02 11:55 160阅读 0赞

题目链接：[https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/][https_leetcode-cn.com_problems_maximum-depth-of-n-ary-tree]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
解法一：迭代

/*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    
    class Solution {
        
    public:
        int maxDepth(Node* root) {
        
            int depth=0;
            if(root==NULL) return depth;
    
            queue<Node*> que;
            que.push(root);
    
            while(!que.empty()){
        
                int size=que.size();
                depth++;
    
                while(size--){
        
                    Node* tmp=que.front();
                    que.pop();
    
                    for(auto e:tmp->children){
        
                        if(e) que.push(e);
                    }
                }
            }
    
            return depth;
        }
    };

解法二：递归

/*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    
    class Solution {
        
    public:
        int maxDepth(Node* root) {
        
            return dfs(root);
        }
        int dfs(Node* root){
        
            if(root==NULL) return 0;
            int depth=0;
    
            for(auto e:root->children){
        
                depth=max(depth,dfs(e));
            }
    
            return depth+1;
        }
    };

[https_leetcode-cn.com_problems_maximum-depth-of-n-ary-tree]: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/6412f258332347a2aa35200b3a7cba5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/0cd7f42ae69d4ccbacd7103a2eb838a7.png