【leetcode.559】N叉樹的最大深度

一、題目描述

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

最大深度是指從根節點到最遠葉子節點的最長路徑上的節點總數。

例如，給定一個 ​

​3叉樹​

​ :

我們應傳回其最大深度，3。

說明:

1. 樹的深度不會超過​

   ​1000​

   ​。
2. 樹的節點總不會超過​

   ​5000​

   ​。

二、思路

采用深度優先搜尋，遞歸擷取子節點的最大深度，接着更新maxRootDepth即可。

該方案的時間複雜度為O(N)，N代表節點總數，空間複雜度為O(1)。

public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.children == null) {
            return 1;
        }
        int rootMaxDepth = 0;
        for (Node children : root.children) {
            //遞歸擷取子節點的最大深度
            int childrenMaxDepth = maxDepth(children);
            //更新max值
            rootMaxDepth = Math.max(rootMaxDepth, childrenMaxDepth);
        }
        return rootMaxDepth + 1;
    }