【二叉樹】N 叉樹的最大深度

0x00 題目

給定一個 N 叉樹，找到其最大深度

最大深度是指從​

​根節點​

​​到最遠​

​葉子節點​

​的最長路徑上的節點總數

說明: 葉子節點是指沒有子節點的節點。

0x01 思路

這個題目跟【二叉樹的最大深度】類似

二叉樹有 2 個節點，N 叉樹節點有多個

由于不知道具體個數，隻能通過循環來周遊每個節點

方式一：

通過循環遞歸子樹，然後記錄最大值。

方式二：

通過層序周遊方式，從目前節點，依次向下尋找。

每往下一層，同時記錄深度。

直到最後一層為空時，則找到了最遠的葉子節點。

0x02 解法

語言：​

​Swift​

​

樹節點：​

​Node​

​

public class Node {
    public var val: Int
    public var children: [Node]
    public init(_ val: Int) {
        self.val = val
        self.children = []
    }
}      

​

​遞歸​

​方式：

func maxDepth(_ root: Node?) -> Int {
    if root == nil { return 0 }
        
    var max = 0
    for child in root!.children {
        let depth = maxDepth(child)
        if depth > max { max = depth }
    }
    return max + 1
}      

func maxDepth(_ root: Node?) -> Int {
    guard let root = root else { return 0 }

    // 深度，因為當 tmp 最後為空時，depth 依舊加了 1，是以初始化為 0
    var depth = 0
    var queue: [Node] = []
    queue.append(root)
    
    while !queue.isEmpty {
        var tmp: [Node] = []
        
        // 添加所有下一層的子節點
        while !queue.isEmpty {
            let node = queue.removeFirst()
        
            for child in node.children {
                tmp.append(child)
            }
        }

        queue = tmp
        depth += 1
    }
    
    return depth
}