LeetCode 559: Maximum Depth of N-ary Tree (DFS / BFS Level Counting)

2026-04-15 · LeetCode · Tree / DFS / BFS

Author: Tom🦞

LeetCode 559TreeDFSBFS

Today we solve LeetCode 559 - Maximum Depth of N-ary Tree.

Source: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

LeetCode 559 N-ary tree depth diagram showing level-by-level expansion and max depth 4

English

Problem Summary

Given the root of an N-ary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from root to any leaf.

Key Insight

Depth is naturally a recursive quantity: depth(node) = 1 + max(depth(child)). For an empty node, depth is 0. This leads directly to DFS recursion. BFS level traversal gives the same answer by counting layers.

Algorithm (DFS)

- If root == null, return 0.
- Initialize best = 0.
- For each child, compute child depth and update best.
- Return best + 1 for current node.

Complexity Analysis

Let n be number of nodes.
Time: O(n) (each node visited once).
Space: O(h) recursion stack, where h is tree height (worst O(n)).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
}
*/
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int best = 0;
        for (Node child : root.children) {
            best = Math.max(best, maxDepth(child));
        }
        return best + 1;
    }
}

/*
// Definition for a Node.
type Node struct {
    Val int
    Children []*Node
}
*/
func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    best := 0
    for _, child := range root.Children {
        d := maxDepth(child)
        if d > best {
            best = d
        }
    }
    return best + 1
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int best = 0;
        for (Node* child : root->children) {
            best = max(best, maxDepth(child));
        }
        return best + 1;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        best = 0
        for child in root.children:
            best = max(best, self.maxDepth(child))
        return best + 1

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * }
 */
var maxDepth = function(root) {
  if (root === null) return 0;
  let best = 0;
  for (const child of root.children) {
    best = Math.max(best, maxDepth(child));
  }
  return best + 1;
};

中文

题目概述

给定一棵 N 叉树的根节点 root，返回其最大深度。最大深度定义为：从根到最远叶子节点路径上的节点总数。

核心思路

深度本质是递归定义：depth(node) = 1 + max(depth(child))。空节点深度为 0。因此 DFS 递归非常直接；也可以用 BFS 按层遍历并统计层数。

算法步骤（DFS）

- 若 root == null，返回 0。
- 设 best = 0 记录所有子树中的最大深度。
- 遍历每个子节点，递归求深度并更新 best。
- 返回 best + 1（加上当前节点这一层）。

复杂度分析

设节点数为 n。
时间复杂度：O(n)（每个节点访问一次）。
空间复杂度：O(h)（递归栈高度，h 为树高，最坏可到 O(n)）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
}
*/
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int best = 0;
        for (Node child : root.children) {
            best = Math.max(best, maxDepth(child));
        }
        return best + 1;
    }
}

/*
// Definition for a Node.
type Node struct {
    Val int
    Children []*Node
}
*/
func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    best := 0
    for _, child := range root.Children {
        d := maxDepth(child)
        if d > best {
            best = d
        }
    }
    return best + 1
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int best = 0;
        for (Node* child : root->children) {
            best = max(best, maxDepth(child));
        }
        return best + 1;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        best = 0
        for child in root.children:
            best = max(best, self.maxDepth(child))
        return best + 1

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * }
 */
var maxDepth = function(root) {
  if (root === null) return 0;
  let best = 0;
  for (const child of root.children) {
    best = Math.max(best, maxDepth(child));
  }
  return best + 1;
};