559. N叉树的最大深度

桃扇骨 2023-02-18 08:03 41阅读 0赞

# 题目来源 #

[559. N叉树的最大深度][559. N]

# 题目解析 #

## 层次遍历 ##

class Solution {
        
        public int maxDepth(Node root) {
        
            if (root == null){
        
                return 0;
            }
            
            int ans = 0;
            LinkedList<Node> list = new LinkedList<>();
            list.offer(root);
            
            while (!list.isEmpty()){
        
                int size = list.size();
                LinkedList<Node> tmp = new LinkedList<>();
                for (int i = 0; i < size; i++){
        
                    Node pop = list.pop();
                    for (Node child : pop.children){
        
                        tmp.offer(child);
                    }
                }
                
                list = tmp;
                ans++;
            }
    
            return ans;   
        }
    }

![在这里插入图片描述][2020061614011076.png]

## 递归 ##

首先来看一种常见的递归解法，就是需要有一个当前深度，然后带一个全局变量res进去。在递归函数中，如果node为空，直接返回。若子结点数组为空，那么结果res和cur比较取较大值。否则就遍历子结点数组，对每个子结点调用递归函数，这里的cur要自增1

class Solution {
        
        private int ans = 0;
        public int maxDepth(Node root) {
        
            helper(root, 1);
            return ans;
        }
    
        private void  helper(Node root, int depth){
        
            if (root == null){
        
                return;
            }
    
            if (root.children.isEmpty()){
        
                ans = Math.max(ans, depth) ;
            }
    
            for (Node child: root.children) {
        
                helper(child, depth + 1);
            }
        }
    }

解法2

public int maxDepth(Node root) {
        
            if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            for (Node child : root.children){
        
                ans = Math.max(ans, maxDepth(child));
            }
    
            return ans + 1;
        }

直接主函数中递归，首先判空，否则就是遍历子结点数组，然后对每个子结点调用递归函数的返回值加1后跟res相比，取较大值更新结果res

class Solution {
        
        public int maxDepth(Node root) {
        
            if (root == null){
        
                return 0;
            }
    
            int ans = 1;
            for (Node child : root.children){
        
                ans = Math.max(ans, maxDepth(child) + 1);
            }
            
            return ans;  
        }
    }

![在这里插入图片描述][20200616140606497.png]

[559. N]: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
[2020061614011076.png]: https://img-blog.csdnimg.cn/2020061614011076.png
[20200616140606497.png]: https://img-blog.csdnimg.cn/20200616140606497.png