剑指offer--559. N叉树的最大深度

喜欢ヅ旅行 2022-12-03 05:13 102阅读 0赞

## 题目描述 ##

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70_pic_center]

我们应返回其最大深度，3。

说明:

树的深度不会超过 1000。  
树的节点总不会超过 5000。

## 思路：递归（深度优先搜索dfs）、迭代（层序遍历） ##

类似的题目还有 **二叉树的深度、平衡二叉树**

遍历多叉树孩子节点的写法

for(Node node : root.children){
        }

## 解决方法 ##

/*
    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;
    
        public Node() {}
    
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    
    class Solution {
        
        public int maxDepth(Node root) {
        
            //递归解决，超出内存限制，明天试试层序遍历
            /**
            if(root == null) return 0;
            int max = 0;
            for(Node node : root.children){ //需要注意遍历多叉树所有孩子节点的写法
                int depth = maxDepth(node);
                max = Math.max(max, depth);
            }
            return max+1;
            **/
            //层序遍历
            if(root == null) return 0;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            int count = 0;
            while(!queue.isEmpty()){
        
                int length = queue.size();
                for(int i=0; i<length; i++){
        
                    Node node = queue.poll();
                    for(Node n:node.children)
                        queue.offer(n);
                }
                count++;
            }
            return count;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3f52938792e447959a8b9a9f92c4c83a.png