559_N叉樹的最大深度

559_N叉樹的最大深度

package 二叉樹.BT;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
 * 
 * @author Huangyujun
 *
 */
public class _559_N叉樹的最大深度 {
    public class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }


 //這樣是不對的（原因想不明白）：官網是把每個孩子結點的maxDepth 存儲起來，最後才去拿那個最大值
    //正解：周遊每個孩子前  height 必須等于  1;
    int height = 0;
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;
        } else {
            height = 1;
            for (Node node : root.children) {    //知道原因了孩子是同一級的：1 + maxDepth(node)
                height = Math.max(height, 1 + maxDepth(node));
                
            }
        }
        return height;
    }

    class Solution {
          public int maxDepth(Node root) {
            if (root == null) {
              return 0;
            } else if (root.children.isEmpty()) {
              return 1;  
            } else {
              List<Integer> heights = new LinkedList<>();
              for (Node item : root.children) {
                heights.add(maxDepth(item)); 
              }
              return Collections.max(heights) + 1;
            }
          }
        }

    //疊代法
    public int maxDepth2(Node root) {
        if(root == null) return 0;
        int height = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int levelSize = 1;
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            levelSize--;
            for(int i = 0; i < node.children.size(); i++) {
                if(node.children.get(i) != null)
                queue.add(node.children.get(i));
            }
            if(levelSize == 0){
                height++;
                levelSize = queue.size();
            }
        }

        return height; 
    }
// 小知識：
//調用poll()和pop()都可以傳回隊首元素并将其從原隊列删除。不同的是當隊列為空時，調用pop()會抛出異常，而poll()會傳回null
    
    //思路：通過一個類似map 鍵值對的集合，然後，将（結點   深度）的添加進去，然後又通過 
    //棧 （這不是一個純棧）：不斷的：(poll 出來目前結點，然後深度 + 1， add 進去 子結點)
    //poll() 出來，後得到目前結點，将目前結點的深度加 1，然後把目前結點的所有 子結點 添加進棧
    
    
//     public int maxDepth(Node root) {
//         //map的話，無法直接通過 目前取出來一對鍵值對，然後直接擷取其鍵 或 值
//            Queue<Pair<Node, Integer>> stack = new LinkedList<>();
//            if (root != null) {
//              stack.add(new Pair(root, 1));
//            }
//
//            int depth = 0;
//            while (!stack.isEmpty()) {
//              Pair<Node, Integer> current = stack.poll();
//              root = current.getKey();
//              int current_depth = current.getValue();
//              if (root != null) {
//                depth = Math.max(depth, current_depth);
//                for (Node c : root.children) {
//                  stack.add(new Pair(c, current_depth + 1));    
//                }
//              }
//            }
//            return depth;
//          }


}