559. N 叉树的最大深度

题目

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

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

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

难度：🌟🌟🌟

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：

• 树的深度不会超过 1000 。
• 树的节点数目位于 [0, 10⁴] 之间。

题解

思路一：
采取层序遍历思路，每遍历一层就计数一次，直到遍历结束，最后计数的即为最大深度。

思路二：
采用分解问题的思路。

代码实现

type Node struct {
	Val      int
	Children []*Node
}

// 思路一：层序遍历计数
func maxDepth(root *Node) int {
	if root == nil {
		return 0
	}
	queue := NewQueue()
	queue.offer(root)
	var maxDepthNum int
	for !queue.isEmpty() {
		sz := queue.size()
		maxDepthNum++
		for sz > 0 {
			root = queue.pop()
			for _, child := range root.Children {
				queue.offer(child)
			}
			sz--
		}
	}
	return maxDepthNum
}

func NewQueue() *MyQueue {
	return &MyQueue{}
}

type MyQueue struct {
	data []*Node
}

func (q *MyQueue) offer(elem *Node) {
	q.data = append(q.data, elem)
}

func (q *MyQueue) pop() *Node {
	res := q.data[0]
	q.data = q.data[1:]
	return res
}

func (q *MyQueue) size() int {
	return len(q.data)
}

func (q *MyQueue) isEmpty() bool {
	return q.size() == 0
}

// 思路二：递归遍历，分解问题
func maxDepth(root *Node) int {
	if root == nil {
		return 0
	}
	var maxDepthNum int
	for _, child := range root.Children {
		childDepth := maxDepth(child)
		maxDepthNum = max(childDepth, maxDepthNum)
	}
	return maxDepthNum + 1
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}