[LeetCode刷題筆記] 559 – Maximum Depth of N-ary Tree

題目描述:

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Example 1:

img

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

img

Input: 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]
Output: 5

 

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.

  • The total number of nodes is between [0, 104].

一刷題解(Bottom-up Recursion):

        這題需要找到一個N叉樹中的最大深度,我們可以通過Botton-up的Recursion來解決。只要當前節點不為空,就默認有「一層」的存在(curr = 1)。然後嘗試遍歷當前節點下的所有子節點,再對子節點進行調用MaxDepth,一直調用直到再沒有子節點(root == null)。每次調用的成功,都會使該節點的maxDepth記錄值+1,當接觸到N叉樹的底部後,記錄完成的maxDepth會一層一層返回,每次返回我們都對不同分支返回的maxDepth進行取最大值,並加上當前層的1(curr + maxDepth),最後就可以這個N叉樹的最大深度。

public class Solution {
   public int MaxDepth(Node root) {

       if(root == null) { return 0; }

       int curr = 1;

       int maxDepth = 0;    

       for (int i = 0; i < root.children.Count; i++)
      {
//在不同分支中,取深度最大的一支的深度值
           int downStair = MaxDepth(root.children[i]);
           maxDepth = Math.Max(maxDepth, downStair);
      }

       return curr + maxDepth;                
  }
}