559.N叉树的最大深度

链接：559.N叉树的最大深度
难度：Easy
标签：树、深度优先搜索、广度优先搜索
简介：给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：4ms
• 内存消耗：40.7MB
• 编程语言：java
• 解法介绍：层序遍历。

/*
// 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;
		Queue<Node> queue = new LinkedList<Node>();
		int height = 0, size = 1;
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (node.children != null)
				for (int i = 0, len = node.children.size(); i < len; i++)
					queue.offer(node.children.get(i));
			size--;
			if (size == 0) {
				height++;
				size = queue.size();
			}
		}
		return height;
	}
}

题解 2 - typescript

• 编辑时间：2021-11-21
• 执行用时：108ms
• 内存消耗：48.4MB
• 编程语言：typescript
• 解法介绍：dfs。

function maxDepth(root: Node | null): number {
  if (root === null) return 0;
  return Math.max(...root.children.map(node => maxDepth(node)), 0) + 1;
}

题解 3 - c

• 编辑时间：2021-11-21
• 执行用时：4ms
• 内存消耗：6.9MB
• 编程语言：c
• 解法介绍：dfs。

int maxDepth(struct Node* root) {
    if (!root) return 0;
    int ans = 1;
    for (int i = 0; i < root->numChildren; i++) {
        int next_ans = maxDepth(root->children[i]) + 1;
        ans = next_ans > ans ? next_ans : ans;
    }
    return ans;
}