559. Maximum Depth of N-ary Tree

문제 링크: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

이번엔 Binary Tree가 아닌 N-ary Tree의 maximum depth를 구하는 문제이다.
특이한 점은 트리의 각 노드가 아래와 같이 정의되어 있다는 것이다.

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;
    }
}

N-ary Tree이기 때문에, 트리의 각 node는 left와 right 포인터를 가지는 것이 아닌 자식 노드들의 list를 가진다.

Solution

1. DFS (Recursion)

직관적인 방법이다.

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

2. BFS (Iteration)

Maximum Depth of Binary Tree 풀이와 같은 방법으로 Queue를 사용해 maximum depth를 구했다.

Algorithm

1. root node부터 Queue에 삽입한다.
2. Queue의 size만큼 iteration을 수행하며 Queue에 삽입된 front 노드를 poll, 해당 노드의 자식 노드들을 Queue에 offer 한다.
3. 같은 level에 있는 node들을 모두 검사한 후 depth를 증가시킨다.
4. 2~3을 반복한다.

class Solution {
    Queue<Node> queue = new LinkedList<>();

    public int maxDepth(Node root) {
        if(root == null) return 0;

        int depth = 0;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            while(queueSize-- > 0) {
                Node currNode = queue.poll();
                List<Node> children = currNode.children;
                if(children.size() != 0) putChildrenNodeToQueue(children);
            }
            depth++;
        }
        return depth;
    }

    void putChildrenNodeToQueue(List<Node> children) {
        for(Node child : children) {
            queue.offer(child);
        }
    }
}

모든 노드를 방문하니 시간 복잡도는 O(N)이 된다.