原题链接

题目描述:

给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N叉树输入按层序遍历序列化表示，每组子节点由空值分隔.

解题思路:

其实和二叉树的最大深度是一样的逻辑，唯一需要变的是这次追加孩子节点。

golang示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    // 一样使用层序遍历
    if root == nil {
        return 0
    }
    var total int
    queue := []*Node{root}
    for len(queue) > 0 {
        // 该层孩子节点的个数
        currCnt := len(queue)
        // 将该层的节点出列，出完深度+1
        for i := 0; i < currCnt; i++ {
            curNode := queue[0]
            queue = queue[1:]
            // 只要孩子节点不为空，就追加进队列
            if len(curNode.Children) > 0 {
                queue = append(queue, curNode.Children...)
            }
        }
        total += 1
    }
    return total
}