leetcode 559. N 叉树的最大深度（Java版，N叉树的深度优先搜索）

分手后的思念是犯贱 2022-10-15 07:57 146阅读 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

思路是 N 叉树的遍历（深度优先搜索）

/* // 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 { 
        int maxDepth = 0;
    
        public int maxDepth(Node root) { 
            if (root == null) return 0;
            dfs(root, 1);
            return maxDepth;
        }
    
        public void dfs(Node node, int depth) { 
            if (node == null) maxDepth = Math.max(maxDepth, depth);
            for (Node n : node.children) { 
                dfs(n, depth + 1);
            }
            maxDepth = Math.max(maxDepth, depth);
        }
    }

思路相同，但看到评论区有种更整洁的写法，即将 max 作为返回值在递归过程中传递：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221014/c71d8b68719040eca33c7aa7d92b4e70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221014/b6d6d8a4c5c94d86907084ac087ce3e6.png